八大链表OJ笔试题带你手撕单链表

转x33g5p2x  于2022-05-11 转载在 其他  
字(7.0k)|赞(0)|评价(0)|浏览(492)

1. 移除链表元素

方法一：（不带哨兵位的）

代码：

需要考虑的情况：

  1. 正常情况
  2. 链表连续几个节点存储的值都是val
  3. 链表最开始的节点存储的值是val

图示：

正常情况：（经画图之后，正常情况能够处理链表中连续几个节点存储的值都是val的情况）

头节点存储值为val的情况：

  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2. {
  3.     struct ListNode*prev = NULL;
  4.     struct ListNode*cur = head;
  5.     while(cur)
  6.     {
  7.         if(cur->val==val)
  8.         {
  9.             if(prev==NULL)
  10.             {
  11.                 struct ListNode* next = cur->next;
  12.                 free(cur);
  13.                 cur = next;
  14.                 head = cur;
  15.             }
  16.             else
  17.             {
  18.                 prev->next = cur->next;
  19.                 free(cur);
  20.                 cur = prev->next;
  21.             }
  22.             
  23.         }
  24.         else
  25.         {
  26.             prev = cur;
  27.             cur = cur->next;
  28.         }
  29.     }
  30.     return head;
  31. }

方法二：（带哨兵位的）

与前面一种方法进行相比，这种方法更为简单，操作起来难度较小并且代码更为简洁，不需要进行区分上面的三种情况。

代码：

  1. struct ListNode* removeElements(struct ListNode* head, int val)//带哨兵位的
  2. {
  3.     struct ListNode*new = malloc(sizeof(struct ListNode));
  4.     new->next = head;
  5.     struct ListNode*prev = new;
  6.     struct ListNode*cur = head;
  7.     while(cur)
  8.     {
  9.         if(cur->val==val)//需要删除的节点
  10.         {
  11.             struct ListNode*next = cur;//next用来存放cur当前的地址，方便后面进行释放
  12.             cur = cur->next;
  13.             prev->next = cur;
  14.             free(next);
  15.         }
  16.         else//不需要删除的节点
  17.         {
  18.             prev = cur;
  19.             cur = cur->next;
  20.         }
  21.     }
  22.     struct ListNode*tmp = new->next;//暂时存储需要返回的地址
  23.     free(new);//把开辟的哨兵位的空间释放掉
  24.     return tmp;
  25. }

2. 反转链表

方法一：（三个指针反转方向）

图示：

思路：逐个向后进行遍历，在遍历的同时将next指针的指向变为指向前一个指针，同时返回尾节点（反转后新链表的头节点）

  1. struct ListNode* reverseList(struct ListNode* head)
  2. {
  3.     if(head==NULL)//当链表尾空时，返回的是空链表
  4.     {
  5.         return head;
  6.     }
  7.     else
  8.     {
  9.         struct ListNode*prev = NULL;
  10.         struct ListNode*cur = head;
  11.         struct ListNode*next = head->next;
  12.         while(cur)
  13.         {
  14.             cur->next = prev;
  15.             prev = cur;
  16.             cur = next;
  17.             if(next)
  18.                 next = next->next;
  19.         }
  20.         return prev;//返回prev的原因是：当cur为空节点时，cur位于尾节点的下一个，而位于cur的前一个自然就是尾节点，即新的头节点
  21.     }
  22. }

方法二：（头插法）

思路：遍历上面的链表，把节点拿下来头插，但是不创建新的节点。

图示：

注意：此处并没有创建新的节点，其实从本质上来说和上面没有大的区别，只是思想有所差别。

  1. struct ListNode* reverseList(struct ListNode* head)
  2. {
  3.     struct ListNode*newHead = NULL;
  4.     struct ListNode*cur = head;
  5.     
  6.     while(cur)
  7.     {
  8.         struct ListNode*next = cur->next;
  9.         cur->next = newHead;
  10.         newHead = cur;
  11.         cur = next;
  12.     }
  13.     return newHead;
  14. }

3. 链表的中间节点

思路：
使用两个指针，然后使用两个指针进行遍历，快指针一次跳跃两个节点，慢指针一次跳跃一个节点，当快指针遍历完整个数组的时候，慢指针所处的位置就是中间节点所处的位置。

图示：

代码：

  1. struct ListNode* middleNode(struct ListNode* head)
  2. {
  3.     struct ListNode*slow = head;//慢节点
  4.     struct ListNode*fast = head;//快节点
  5.     while(fast&&fast->next)
  6.     {
  7.         fast = fast->next->next;
  8.         slow = slow->next;
  9.     }
  10.     return slow;
  11. }

注意：fast和fast->next是不可以进行互换的，因为只有当fast为空的时候就不可能执行到fast->next，所以也就不会出现对空指针进行解引用的情况，一旦互换之后，就可能出现对空指针进行解引用的情况。

4. 链表中倒数第k个结点

思路：其实这个与前面的寻找链表的中间节点相类似，也是使用快慢指针的方法，使快指针先走k个节点，当快指针走到空指针的位置的时候，慢指针所停留的位置就是我们想要找到的节点。

代码：

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
  2. {
  3.     struct ListNode*fast = pListHead;
  4.     struct ListNode*slow = pListHead;
  5.     while(k--)
  6.     {
  7.         if(fast==NULL)
  8.             return NULL;//当k大于链表的长度时返回空指针NULL
  9.         fast = fast->next;
  10.     }
  11.         
  12.     while(fast)
  13.     {
  14.         fast = fast->next;
  15.         slow = slow->next;
  16.     }
  17.     return slow;
  18. }

注意：

注意下面的两种情况：

  1. 当k大于链表的长度的时候
  2. 当链表为空链表的时候

上面的这两种情况，都是通过if判断来进行解决的。

5. 合并两个有序链表

思路：

代码：（这是不带哨兵位的）

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  2. {
  3.     if(list1==NULL)
  4.     {
  5.         return list2;
  6.     }
  7.     if(list2==NULL)
  8.     {
  9.         return list1;
  10.     }
  11.     struct ListNode*tail = NULL;
  12.     struct ListNode*head = tail;
  13.     while(list1&&list2)
  14.     {
  15.         if(list1->val<list2->val)
  16.         {
  17.             if(tail==NULL)
  18.                 head = tail = list1;
  19.             else
  20.             {
  21.                 tail->next = list1;
  22.                 tail = list1;
  23.             }
  24.             list1 = list1->next;
  25.         }
  26.         else
  27.         {
  28.             if(tail==NULL)
  29.                 head = tail = list2;
  30.             else
  31.             {
  32.                 tail->next = list2;
  33.                 tail = list2;
  34.             }
  35.             list2 = list2->next;
  36.         }
  37.     }
  38.     if(list1)
  39.     {
  40.         tail->next = list1;
  41.     }
  42.     if(list2)
  43.     {
  44.         tail->next = list2;
  45.     }
  46.     return head;
  47. }

（带哨兵位的）

图示：

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  2. {
  3.     struct ListNode*tail = (struct ListNode*)malloc(sizeof(struct ListNode));
  4.     struct ListNode*head = tail;
  5.     head->next = NULL;
  6.     while(list1&&list2)
  7.     {
  8.         if(list1->val<list2->val)
  9.         {
  10.             tail->next = list1;
  11.             tail = list1;
  12.             list1 = list1->next;
  13.         }
  14.         else
  15.         {
  16.             tail->next = list2;
  17.             tail = list2;
  18.             list2 = list2->next;
  19.         }
  20.     }
  21.     if(list1)
  22.     {
  23.         tail->next = list1;
  24.     }
  25.     if(list2)
  26.     {
  27.         tail->next = list2;
  28.     }
  29.     return head->next;
  30. }

6. 链表分割

思路：对原链表进行遍历，然后将小于x的形成一个链表，大于x的形成一个链表，然后将两个链表连接起来就是我们要返回的新链表。

方法一：（带哨兵位的）

图示：

代码：

  1. ListNode* partition(ListNode* pHead, int x) 
  2. {
  3.     struct ListNode* lessTail = (struct ListNode*)malloc(sizeof(ListNode));//作为结尾
  4.     struct ListNode* lessHead = lessTail;//指向新的节点存储元素的值均比x小的链表
  5.     struct ListNode* greaterTail = (struct ListNode*)malloc(sizeof(ListNode));//作为结尾
  6.     struct ListNode* greaterHead = greaterTail;//指向新的节点存储元素的值均比x大或者等于的链表
  7.     struct ListNode* cur = pHead;//用来遍历所给链表的指针
  8.     while (cur)//判断所给链表遍历是否终止
  9.     {
  10.         if (cur->val < x)//连接比x小的链表节点
  11.         {
  12.             lessTail->next = cur;
  13.             lessTail = lessTail->next;
  14.         }
  15.         else//连接大于或者等于x的链表节点
  16.         {
  17.             greaterTail->next = cur;
  18.             greaterTail = greaterTail->next;
  19.         }
  20.         cur = cur->next;
  21.     }
  22.     lessTail->next = greaterHead->next;//连接两个链表形成最后的结果链表
  23.     greaterTail->next = NULL;//将最后一个节点的next置为空
  24.     struct ListNode* list = lessHead->next;//存储返回值，方便free掉开辟的空间
  25.     free(lessHead);
  26.     free(greaterHead);
  27.     return list;
  28. }

方法二：（不带哨兵位的）

图示：

1、正常情况：

2、当存储比x小的链表为空时

3、当存储大于x的链表为空时

代码：

  1. ListNode* partition(ListNode* pHead, int x)
  2. {
  3. 	struct ListNode* lessHead = NULL;
  4. 	struct ListNode* lessTail = NULL;
  5. 	struct ListNode* greaterHead = NULL;
  6. 	struct ListNode* greaterTail = NULL;
  7. 	struct ListNode* cur = pHead;
  8. 	while (cur)
  9. 	{
  10. 		if (cur->val < x)
  11. 		{
  13. 			if (lessHead == NULL)
  14. 			{
  15. 				lessTail = cur;
  16. 				lessHead = cur;
  17. 			}
  18. 			else
  19. 			{
  20. 				lessTail->next = cur;
  21. 				lessTail = cur;
  22. 			}
  23. 		}
  24. 		else
  25. 		{
  27. 			if (greaterHead == NULL)
  28. 			{
  29. 				greaterTail = cur;
  30. 				greaterHead = cur;
  32. 			}
  33. 			else
  34. 			{
  35. 				greaterTail->next = cur;
  36. 				greaterTail = cur;
  37. 			}
  38. 		}
  39. 		cur = cur->next;
  40. 	}
  41. 	//应当有三种情况
  42. 	//1、存储小于x的链表为空，存储大于x的链表不为空
  43. 	//2、存储小于x的链表不为空，存储大于x的链表为空
  44. 	//3、存储小于x和存储小于x的链表均不为空
  45. 	//后面的两种方法是可以合并的，因为都要进行两个链表的连接，无论存储大于x的链表是否为空，都不影响最后的结果
  46. 	if (lessTail == NULL)//判断是否是没有小于x的数据，如果是这种情况，那么就返回存储大于x数据的链表
  47. 	{
  48. 		return greaterHead;
  49. 	}
  50. 	
  51. 	lessTail->next = greaterHead;//将两个链表进行连接
  52. 	if (greaterHead != NULL)
  53. 	{
  54. 		greaterTail->next = NULL;//将存储大于x的数据的最后一个节点的next置为空指针
  55. 	}
  56. 	//为什么要进行判定，因为如果直接执行greaterTail->next = NULL属于非法操作，因为当greaterHead等于NULL时，greaterTail也是空指针，执行这行代码就属于对空指针的解引用，属于非法操作
  57. 	return lessHead;
  58. }

7. 链表的回文结构

思路：(偶数个节点一定不会出现问题，很容易就能想到)

代码：

  1. struct ListNode* middleNode(struct ListNode* head)//求中间节点
  2. {
  3. 	struct ListNode* slow = head;//慢节点
  4. 	struct ListNode* fast = head;//快节点
  5. 	while (fast && fast->next)
  6. 	{
  7. 		fast = fast->next->next;
  8. 		slow = slow->next;
  9. 	}
  10. 	return slow;
  11. }
  12. struct ListNode* reverseList(struct ListNode* head)//反转链表
  13. {
  14. 	if (head == NULL)//当链表尾空时，返回的是空链表
  15. 	{
  16. 		return head;
  17. 	}
  18. 	else
  19. 	{
  20. 		struct ListNode* prev = NULL;
  21. 		struct ListNode* cur = head;
  22. 		struct ListNode* next = head->next;
  23. 		while (cur)
  24. 		{
  25. 			cur->next = prev;
  26. 			prev = cur;
  27. 			cur = next;
  28. 			if (next)
  29. 				next = next->next;
  30. 		}
  31. 		return prev;
  32. 	}
  33. }
  34. bool chkPalindrome(ListNode* head) {
  35. 	struct ListNode* mid = middleNode(head);//记录中间节点
  36. 	mid = reverseList(mid);//将反转后的新的节点的起始位置赋值给mid
  37. 	struct ListNode* cur = head;//用来从头遍历链表
  38. 	while (head && mid)
  39. 	{
  40. 		if (head->val != mid->val)
  41. 			return false;
  42. 		head = head->next;
  43. 		mid = mid->next;
  44. 	}
  45. 	return true;
  46. }//此处是C++的，true代表1，false代表0

8. 相交链表

思路：
第一种方法（不推荐）：用listA的每一个节点和listB的每一个节点的地址进行遍历比较，既能判断出是否相交，同时也能找到相交的节点。

第二种方法：先从头找到尾对两个节点同时进行遍历，同时记录两个链表各自的节点数，最后将尾节点进行比较，如果尾节点相同，说明有相交节点，如果不相同，就说明没有相交节点，同时计算出两个链表节点数目的差值，然后使用快慢指针的方法，让较长的链表先走差值步，然后再同时走，两个指针相同的那个点就是我们要求的两个链表相加的点。

图示：

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode*tailA = headA;//记录链表A的尾节点
  3.     struct ListNode*tailB = headB;//记录链表B的尾节点
  4.     int lenA = 1;//记录链表A的长度
  5.     int lenB = 1;//记录链表B的长度
  6.     while(tailA->next!=NULL)
  7.     {
  8.         tailA = tailA->next;
  9.         lenA++;
  10.     }
  11.     while(tailB->next!=NULL)
  12.     {
  13.         tailB = tailB->next;
  14.         lenB++;
  15.     }
  16.     
  17.     if(tailA!=tailB)//尾节点不等，所以直接返回NULL
  18.     {
  19.         return NULL;
  20.     }
  21.     //相交，求节点，长的先走差距步，再同时走找交点
  22.     struct ListNode*shortList = headA,*longList = headB;//默认B是较长节点的链表，A是较短的
  23.     if(lenA>lenB)
  24.     {
  25.         longList = headA;
  26.         shortList = headB;
  27.     }
  28.     int gap = abs(lenA - lenB);//gap存储的是节点数的差值
  30.     while(gap--)
  31.     {
  32.         longList = longList->next;//节点数多的先走gap步
  33.     }
  34.     while(longList!=shortList)//两者同时开始进行遍历，在交点处停下
  35.     {
  36.         longList = longList->next;
  37.         shortList = shortList->next;
  38.     }
  39.     return longList;//随便返回一个就行，因为两个都是交点
  40. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/m0_57304511/article/details/124646380

内容来源于网络，如有侵权，请联系作者删除！

数据结构c++算法链表后端

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com