您现在的位置是:首页 >技术教程 >数据结构之单链表oJ练习网站首页技术教程

数据结构之单链表oJ练习

万众☆倾倒 2023-06-20 04:00:03
简介数据结构之单链表oJ练习

目录

1.移除单链表中与给数相同的元素

2.反转链表

3.找中间节点

4.找倒数第k个

5.合并两个有序链表

6.链表分割

7.链表的回文结构

8.找公共节点


1.移除单链表中与给数相同的元素

 解题思路:

初始化一个新链表,从头结点开始遍历,若相同,保存下一节点位置,再free 掉该节点,若不同将节点赋值给新链表。

代码段:

struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head == NULL)
        return NULL;
    
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    
    while(cur)
    {
        //如果当前节点是需要删除的节点
        if(cur->val == val)
        {
            //首先保存下一个节点
            struct ListNode* next = cur->next;
            //如果删除的为头节点,更新头节点
            //否则让当前节点的前趋节点链接next节点
            if(prev == NULL)
            {
                head = cur->next;
            }
            else
            {
                prev->next = cur->next;  
            }
            //释放当前节点,让cur指向next
            free(cur);
            cur = next;
        }
        else
        {
            //如果cur不是需要删除的节点,则更新prev,cur
            prev = cur;
            cur = cur->next;
        }
    }
    
    return head;
}

2.反转链表

 解题思路:

1.链表逆置,将两个相邻的节点交换位置,交换n-1次,完成链表逆置。

代码段:

struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;
    
    struct ListNode* n1, *n2, *n3;
    n1 = head;
    n2 = n1->next;
    n3 = n2->next;
    n1->next = NULL;
    //中间节点不为空,继续修改指向
    while(n2)
    {
        //中间节点指向反转
        n2->next = n1;
        //更新三个连续的节点
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
    //返回新的头
    return n1;
}

2.头插法,从第一个节点开始遍历,作为新链表的尾节点,然后每遍历一个,头插该节点在新链表中。

// 取节点头插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插新节点,更新头
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    
    return newhead;
}

3.找中间节点

解题思路:

快慢指针:给一个快指针与慢指针都是从链表的头节点开始遍历,快指针每次遍历两个节点,慢指针每次遍历一个节点,当快指针遍历结束时,慢指针刚好处于节点,返回慢指针。

这里需要考虑一下节点总数对于奇偶情况,若为奇数节点快指针刚好为NULL时,慢指针为中间。若为偶指针,则快指针的next为空时,慢指针为中间指针。

所以循环条件为两个都不为零时,即其中一个为零就是中间指针。

truct ListNode* middleNode(struct ListNode* head){
    struct ListNode* faster=head;
    struct ListNode* fast=head;
    while(faster &&faster->next)
    { 
      fast=fast->next;
      faster=faster->next->next;
     
    }
    return fast;
}

4.找倒数第k个

解题思路:

与找中间节点的思路相同,当快指针指向第k个节点时,慢指针指向第一个节点,开始遍历,当快指针为NULL时,慢指针为该链表中倒数第k个节点。

 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* fast=pListHead;
    struct ListNode* slow =pListHead;
    while(k--)
    {
         if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
       }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

5.合并两个有序链表

 

 解题思路:

尾插法:因为是有序链表,我们直接从前开始比较:给定两个指针分别指向链表一与链表二,这里返回的时第三个新链表,则让第一个指针指向节点的数与第二个指针指向节点的数作比较,谁小谁先插,将较小的那个数的节点尾插在链表三之后,之后第一个指针与第二个指针同时继续往后遍历,等到其中一个先遍历完的时候,将另一个指针指向的节点直接尾插到链表三中。若某一链表为空,则返回另外一个。

struct ListNode* mergeTwoLists(struct ListNode*list1, struct ListNode* list2){
struct ListNode*p1=list1;
struct ListNode*p2=list2;
        if(p1 == NULL)
            return p2;
        else if(p2 == NULL)
           return p1;
             
        struct ListNode* head = NULL, *tail = NULL;
        //创建空链表
    	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
        tail->next = NULL;
        while(p1 && p2)
        {
            // 取小的进行尾插
            if(p1->val < p2->val)
            {
                tail->next = p1;
                tail = tail->next;

                p1 = p1->next;
            }
            else
            {
                tail->next = p2;
                tail = tail->next;

                p2 = p2->next;
            }
        }
        //剩余元素直接拼接
        if(p1)
            tail->next = p1;
        else
            tail->next = p2;

      struct ListNode* list = head->next;
        free(head);
        return list;
}

6.链表分割

 解题思路:

创建新链表时为了避免头节点判空这一繁琐的步骤,我们创建两个带哨兵位的链表,从已知链表头节点开始遍历,将小于x的该节点重新放在一个链表内,其余大于等于x按原顺序放在另一个链表内,之后free掉哨兵位,合并两个链表,尾节点置空,返回新头节点。

 

 if(pHead == NULL)
            return NULL;
        
        struct ListNode* lessHead, *lessTail,*greaterHead, *greaterTail;
        //创建链表表头
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while(cur)
        {
            //小于x的尾插到lessTail
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            //大于等于x的尾插到greaterTail
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        //链接两个链表
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        //获取表头
        pHead = lessHead->next;
        free(lessHead);
        free(greaterHead);
        
        return pHead;
    }

7.链表的回文结构

 解题思路:

所谓回文结构就是链表是否对称,因此我们首先需要找的中间节点,将中间节点前的存放在一个链表内,将中间节点包括在中间节点逆置后放在另一个链表中,两链表比对,若有其中一个不相等返回false,孙环结束后返回true。

对于链表奇偶情况时,无论奇偶带有中间节点的比较长,而逆置后与前半部分对比,要么刚好,要么提前结束,不影响对称性。

class PalindromeList {
public:
	bool chkPalindrome(ListNode* A) {
		if (A == NULL || A->next == NULL)
			return true;
		ListNode* slow, *fast, *prev, *cur, *tmp;
		slow = fast = A;
		//找到中间节点
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		prev = NULL;
		//后半部分逆置
		cur = slow;
		while (cur)
		{
			tmp = cur->next;
			cur->next = prev;
			prev = cur;
			cur = tmp;
		}
		//逐点比对
		while (A && prev)
		{
			if (A->val != prev->val)
				return false;
			A = A->next;
			prev = prev->next;
		}
		return true;
	}
};

8.找公共节点

 

 解题思路:本题可直接暴力求解,分别计算出A B两链表的长度,它们的长度差作为较长那个链表便利的条件,即两链表同长度开始比较,若相等则是公共节点,注意这里相同的是结点的地址。

 

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* pa=headA;
    struct ListNode* pb=headB;
    int m=0,n=0;
    while(pa)
    {
        pa=pa->next;
        m ++;
    }
    while(pb)
    {
        pb=pb->next;
        n++;
    }
    int x=m-n;
    struct ListNode* a=headA;
    struct ListNode* b=headB;
    if(x>0)
    {
        while(x--)
        {
            a=a->next;
        }
        while(a)
        {
            if(a==b)
            {
                return a;
            }
            a=a->next;
            b=b->next;
        }
    }else if(x<0)
    {
        while(x++)
        {
            b=b->next;
        }
        while(b)
        {
            if(a==b)
            {
                return b;
            }
            a=a->next;
            b=b->next;
        }
    }else if(x==0)
    {
        while(a)
        {
            if(a==b)
        {
            return a;
           
        } a=a->next;
         b=b->next;
        }
        
    }
        return NULL;
    }

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。