devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

[数据结构]链表OJ(leetcode)_数据结构oj

作者：繁依Fanyi0 | 2024-06-07 01:01:44

赞

踩

数据结构oj

目录

数据结构之链表OJ：：

                                     1.移除链表元素

                                     2.反转链表

                                     3.链表的中间结点

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

                                     5.合并两个有序链表

                                     6.链表分割

                                     7.链表的回文结构

                                     8.相交链表

                                     9.环形链表

                                    10.环形链表II

                                    11.复制带随机指针的链表

数据结构之链表OJ：：

1.移除链表元素

  1. //删除链表中等于给定值val的所有结点
  2. struct ListNode
  3. {
  4. 	int val;
  5. 	struct ListNode* next;
  6. };
  7. //方法一
  8. struct ListNode* removeElements(struct ListNode* head, int val)
  9. {
  10. 	struct ListNode* cur = head, * prev = NULL;
  11. 	while (cur != NULL)
  12. 	{
  13. 		//1.头删
  14. 		//2.非头删
  15. 		if (cur->val == val)
  16. 		{
  17. 			if (cur == head)
  18. 			{
  19. 				head = head->next;
  20. 				free(cur);
  21. 				cur = head;
  22. 			}
  23. 			else
  24. 			{
  25. 				prev->next = cur->next;
  26. 				free(cur);
  27. 				cur = prev->next;
  28. 			}
  29. 		}
  30. 		else
  31. 		{
  32. 			prev = cur;
  33. 			cur = cur->next;
  34. 		}
  35. 	}
  36. 	return head;
  37. }
  38. //不用二级指针的方法:返回头指针
  39. //main函数调用方式:plist = removeElements(plist,6);
  40. //方法二
  41. struct ListNode* removeElements(struct ListNode* head, int val)
  42. {
  43. 	struct ListNode* cur = head;
  44. 	struct ListNode* newhead = NULL;
  45. 	struct ListNode* tail = NULL;
  46. 	while (cur != NULL)
  47. 	{
  48. 		if (cur->val != val)
  49. 		{
  50. 			if (newhead == NULL)
  51. 			{
  52. 				newhead = cur;
  53. 				tail = newhead;
  54. 				cur = cur->next;
  55. 			}
  56. 			else
  57. 			{
  58. 				tail->next = cur;
  59. 				cur = cur->next;
  60. 				tail = tail->next;
  61. 			}
  62. 		}
  63. 		else
  64. 		{
  65. 			struct ListNode* del = cur;
  66. 			cur = cur->next;
  67. 			free(del);
  68. 		}
  69. 	}
  70. 	if (tail != NULL)
  71. 	{
  72. 		tail->next = NULL;
  73. 	}
  74. 	return newhead;
  75. }
  76. //方法三:
  77. struct ListNode* removeElements(struct ListNode* head, int val)
  78. {
  79. 	struct ListNode* cur = head;
  80. 	struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
  81. 	struct ListNode* tail = guard;
  82. 	while (cur != NULL)
  83. 	{
  84. 		if (cur->val != val)
  85. 		{
  86. 			tail->next = cur;
  87. 			tail = tail->next;
  88. 			cur = cur->next;
  89. 		}
  90. 		else
  91. 		{
  92. 			struct ListNode* del = cur;
  93. 			cur = cur->next;
  94. 			free(del);
  95. 		}
  96. 	}
  97. 	//最后结点是val 就会出现此问题
  98. 	if (tail != NULL)
  99. 	{
  100. 		tail->next = NULL;
  101. 	}
  102. 	head = guard->next;
  103. 	free(guard);
  104. 	return head;
  105. }
  106. //替代我们之前实现的二级指针
  107. //1.返回新的链表头 2.设计为带哨兵位

2.反转链表

 

  1. //反转链表
  2. //方法一:取结点头插到新链表
  3. struct ListNode* reverseList(struct ListNode* head)
  4. {
  5. 	struct ListNode* cur = head;
  6. 	struct ListNode* newhead = NULL;
  7. 	while (cur)
  8. 	{
  9. 		struct ListNode* next = cur->next;
  10. 		cur->next = newhead;
  11. 		newhead = cur;
  12. 		cur = next;
  13. 	}
  14. 	return newhead;
  15. }
  16. //方法二:翻转链表方向
  17. struct ListNode* reverseList(struct ListNode* head)
  18. {
  19. 	struct ListNode* prev = NULL;
  20. 	struct ListNode* cur = head;
  21. 	struct ListNode* next = NULL;
  22. 	while (cur)
  23. 	{
  24. 		next = cur->next;
  25. 		cur->next = prev;
  26. 		prev = cur;
  27. 		cur = next;
  28. 	}
  29. 	return prev;
  30. }

3.链表的中间结点

  1. //方法一:
  2. struct ListNode* middleNode(struct ListNode* head)
  3. {
  4. 	struct ListNode* slow = head;
  5. 	struct ListNode* fast = head;
  6. 	while (fast && fast->next)
  7. 	{
  8. 		slow = slow->next;
  9. 		fast = fast->next->next;
  10. 	}
  11. 	return slow;
  12. }
  13. //方法二:
  14. struct ListNode* middleNode(struct ListNode* head)
  15. {
  16.     struct ListNode* cur1 = head;
  17.     int num = 0;
  18.     int mid = 0;
  19.     while (cur1 != NULL)
  20.     {
  21.         num++;
  22.         cur1 = cur1->next;
  23.     }
  24.     mid = num / 2 + 1;
  25.     cur1 = head;
  26.     for (int i = 1; i < mid; i++)
  27.     {
  28.         cur1 = cur1->next;
  29.     }
  30.     return cur1;
  31. }

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

 

  1. //方法一:
  2. struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k) 
  3. {
  4. 	
  5. 	struct ListNode* cur = pListHead;
  6.     int n = 0;
  7.     while (cur)
  8.     {
  9.         n++;
  10.         cur = cur->next;
  11.     }
  12.     if (k > n)
  13.     {
  14.         return NULL;
  15.     }
  16.     cur = pListHead;
  17.     int pos = n - k + 1;
  18.     for (int i = 1; i < pos; i++)
  19.     {
  20.         cur = cur->next;
  21.     }
  22.     return cur;
  23. }
  24. //方法二:
  25. struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k)
  26. {
  27. 	struct ListNode* fast, * slow;
  28. 	fast = slow = pListHead;
  29. 	while (k--) //走k步
  30. 	{
  31. 		//k大于链表长度
  32. 		if (fast == NULL)
  33. 			return NULL;
  34. 		fast = fast->next;
  35. 	}
  36. 	while (fast)
  37. 	{
  38. 		slow = slow->next;
  39. 		fast = fast->next;
  40. 	}
  41. 	return slow;
  42. }
  43. //方法三:
  44. struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k)
  45. {
  46.     struct ListNode* fast = pListHead;
  47.     struct ListNode* slow = pListHead;
  48.     while (--k)
  49.     {
  50.         if (fast == NULL)
  51.         {
  52.             return NULL;
  53.         }
  54.         fast = fast->next;
  55.     }
  56.     if (fast == NULL)
  57.     {
  58.         return NULL;
  59.     }
  60.     while (fast->next)
  61.     {
  62.         fast = fast->next;
  63.         slow = slow->next;
  64.     }
  65.     return slow;
  66. }

5.合并两个有序链表 

  1. //合并两个有序链表
  2. //不带哨兵位
  3. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  4. {
  5. 	if (list1 == NULL)
  6. 	{
  7. 		return list2;
  8. 	}
  9. 	if (list2 == NULL)
  10. 	{
  11. 		return list1;
  12. 	}
  13. 	struct ListNode* begin1 = list1;
  14. 	struct ListNode* begin2 = list2;
  15. 	struct ListNode* newlist = NULL;
  16. 	struct ListNode* begin3 = newlist;
  17. 	while (begin1 != NULL && begin2 != NULL)
  18. 	{
  19. 		if (newlist == NULL)
  20. 		{
  21. 			if (begin1->val < begin2->val)
  22. 			{
  23. 				newlist = begin1;
  24. 				begin1 = begin1->next;
  25. 				begin3 = newlist;
  26. 			}
  27. 			else
  28. 			{
  29. 				newlist = begin2;
  30. 				begin2 = begin2->next;
  31. 				begin3 = newlist;
  32. 			}
  33. 		}
  34. 		else
  35. 		{
  36. 			if (begin1->val < begin2->val)
  37. 			{
  38. 				begin3->next = begin1;
  39. 				begin1 = begin1->next;
  40. 				begin3 = begin3->next;
  41. 			}
  42. 			else
  43. 			{
  44. 				begin3->next = begin2;
  45. 				begin2 = begin2->next;
  46. 				begin3 = begin3->next;
  47. 			}
  48. 		}
  49. 	}
  50. 	if (begin1 == NULL)
  51. 	{
  52. 		begin3->next = begin2;
  53. 	}
  54. 	if (begin2 == NULL)
  55. 	{
  56. 		begin3->next = begin1;
  57. 	}
  58. 	return newlist;
  59. }
  60. //带哨兵位
  61. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  62. {
  63. 	struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
  64. 	guard->next = NULL;
  65. 	struct ListNode* tail = guard;
  66. 	struct ListNode* begin1 = list1;
  67. 	struct ListNode* begin2 = list2;
  68. 	while (begin1 && begin2)
  69. 	{
  70. 		if (begin1->val < begin2->val)
  71. 		{
  72. 			tail->next = begin1;
  73. 			begin1 = begin1->next;
  74. 			tail = tail->next;
  75. 		}
  76. 		else
  77. 		{
  78. 			tail->next = begin2;
  79. 			begin2 = begin2->next;
  80. 			tail = tail->next;
  81. 		}
  82. 	}
  83. 	if (begin1)
  84. 	{
  85. 		tail->next = begin1;
  86. 	}
  87. 	if (begin2)
  88. 	{
  89. 		tail->next = begin2;
  90. 	}
  91. 	struct ListNode* head = guard->next;
  92. 	free(guard);
  93. 	return head;
  94. }

6.链表分割 

  1. //链表分割
  2. struct ListNode* partition(struct ListNode* pHead, int x)
  3. {
  4. 	struct ListNode* lessGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
  5. 	struct ListNode* lessTail = lessGuard;
  6. 	struct ListNode* greaterGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
  7. 	struct ListNode* greaterTail = greaterTail;
  8. 	lessGuard->next = NULL;
  9. 	greaterGuard->next = NULL;
  10. 	struct ListNode* cur = pHead;
  11. 	while (cur)
  12. 	{
  13. 		if (cur->val < x)
  14. 		{
  15. 			lessTail->next = cur;
  16. 			cur = cur->next;
  17. 			lessTail = lessTail->next;
  18. 		}
  19. 		else
  20. 		{
  21. 			greaterTail->next = cur;
  22. 			cur = cur->next;
  23. 			greaterTail = greaterTail->next;
  24. 		}
  25. 	}
  26. 	lessTail->next = greaterGuard->next;
  27. 	greaterTail->next = NULL;
  28. 	pHead = lessGuard->next;
  29. 	free(greaterGuard);
  30. 	greaterGuard = NULL;
  31. 	free(lessGuard);
  32. 	lessGuard = NULL;
  33. 	return pHead;
  34. }

7.链表的回文结构 

 

  1. //链表的回文结构
  2. //方法一:找中间结点翻转链表
  3. struct ListNode* middleNode(struct ListNode* head)
  4. {
  5. 	struct ListNode* slow = head;
  6. 	struct ListNode* fast = head;
  7. 	while (fast && fast->next)
  8. 	{
  9. 		slow = slow->next;
  10. 		fast = fast->next->next;
  11. 	}
  12. 	return slow;
  13. }
  14. struct ListNode* reverseList(struct ListNode* head)
  15. {
  16. 	struct ListNode* prev = NULL;
  17. 	struct ListNode* cur = head;
  18. 	struct ListNode* next = NULL;
  19. 	while (cur)
  20. 	{
  21. 		next = cur->next;
  22. 		cur->next = prev;
  23. 		prev = cur;
  24. 		cur = next;
  25. 	}
  26. 	return prev;
  27. }
  28. bool chkPalindrome(struct ListNode* head)
  29. {
  30. 	struct ListNode* mid = middleNode(head);
  31. 	struct ListNode* rmid = reverseList(mid);
  32. 	while (head && rmid)
  33. 	{
  34. 		if (head->val != rmid->val)
  35. 			return false;
  36. 		head = head->next;
  37. 		rmid = rmid->next;
  38. 	}
  39. 	return true;
  40. }
  41. //方法二:
  42. struct ListNode* reverseList(struct ListNode* head)
  43. {
  44. 	struct ListNode* prev = NULL;
  45. 	struct ListNode* cur = head;
  46. 	struct ListNode* next = NULL;
  47. 	while (cur)
  48. 	{
  49. 		next = cur->next;
  50. 		cur->next = prev;
  51. 		prev = cur;
  52. 		cur = next;
  53. 	}
  54. 	return prev;
  55. }
  56. bool isPalindrome(struct ListNode* head)
  57. {
  58. 	struct ListNode* cur = head;
  59. 	struct ListNode* copyGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
  60. 	copyGuard->next = NULL;
  61. 	struct  ListNode* copyTail = copyGuard;
  62. 	while (cur)
  63. 	{
  64. 		struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
  65. 		newnode->val = cur->val;
  66. 		copyTail->next = newnode;
  67. 		copyTail = copyTail->next;
  68. 	}
  69. 	copyTail->next = NULL;
  70. 	struct ListNode* rhead = reverseList(copyGuard->next);
  71. 	while (rhead || head)
  72. 	{
  73. 		if (rhead->val != head->val)
  74. 		{
  75. 			return false;
  76. 		}
  77. 		rhead = rhead->next;
  78. 		head = head->next;
  79. 	}
  80. 	free(copyGuard);
  81. 	copyGuard = NULL;
  82. 	return true;
  83. }

8.相交链表 

  1. //方法一:
  2. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  3. {
  4.     struct ListNode* curA = headA;
  5. 	struct ListNode* curB = headB;
  6. 	while(curA != NULL)
  7.     {
  8.         while(curB != NULL)
  9.         {
  10.             if(curA == curB)
  11.             {
  12.                 return curA;
  13.             }
  14.             curB = curB->next;
  15.         }
  16.         curB = headB;
  17.         curA = curA->next;
  18.     }
  19. 	return NULL;
  20. }
  21. //方法二:
  22. struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
  23. {
  24. 	if (headA == NULL || headB == NULL)
  25. 	{
  26. 		return NULL;
  27. 	}
  28. 	struct ListNode* curA = headA;
  29. 	struct ListNode* curB = headB;
  30. 	int lenA = 1;
  31. 	while(curA->next)
  32. 	{
  33. 		curA = curA->next;
  34. 		lenA++;
  35. 	}
  36. 	int lenB = 1;
  37. 	while (curB->next)
  38. 	{
  39. 		curB = curB->next;
  40. 		lenB++;
  41. 	}
  42. 	if (curA != curB)
  43. 	{
  44. 		return NULL;
  45. 	}
  46. 	struct ListNode* longList = headA;
  47. 	struct ListNode* shortList = headB;
  48. 	if (lenA < lenB)
  49. 	{
  50. 		longList = headB;
  51. 		shortList = headA;
  52. 	}
  53. 	int gap = abs(lenA - lenB);
  54. 	while (gap--)
  55. 	{
  56. 		longList = longList->next;
  57. 	}
  58. 	while (longList != shortList)
  59. 	{
  60. 		longList = longList->next;
  61. 		shortList = shortList->next;
  62. 	}
  63. 	return longList;
  64. }

9.环形链表 

 

 

  1. //环形链表
  2. //快慢指针法:slow进环以后 fast开始追赶slow 
  3. bool hasCycle(struct ListNode* head)
  4. {
  5. 	struct ListNode* fast = head;
  6. 	struct ListNode* slow = head;
  7. 	while (fast && fast->next)
  8. 	{
  9. 		fast = fast->next->next;
  10. 		slow = slow->next;
  11. 		if (slow == fast)
  12. 		{
  13. 			return true;
  14. 		}
  15. 	}
  16. 	return false;
  17. }

10.环形链表II

  1. //环形链表II
  2. //方法一:公式证明推导
  3. struct ListNode* detectCycle(struct ListNode* head)
  4. {
  5. 	struct ListNode* slow = head;
  6.     struct ListNode* fast = head;
  7. 	while (fast && fast->next)
  8. 	{
  9. 		slow = slow->next;
  10. 		fast = fast->next->next;
  11. 		if (slow == fast)
  12. 		{
  13. 			struct ListNode* meet = slow;
  14. 			while (meet != head)
  15. 			{
  16. 				meet = meet->next;
  17. 				head = head->next;
  18. 			}
  19. 			return meet;
  20. 		}
  21. 	}
  22. 	return NULL;
  23. }
  24. //方法二:转换成相交问题
  25. struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
  26. {
  27. 	if (headA == NULL || headB == NULL)
  28. 	{
  29. 		return NULL;
  30. 	}
  31. 	struct ListNode* curA = headA, * curB = headB;
  32. 	int lenA = 1;
  33. 	//找尾结点
  34. 	while (curA->next)
  35. 	{
  36. 		curA = curA->next;
  37. 		lenA++;
  38. 	}
  39. 	int lenB = 1;
  40. 	while (curB->next)
  41. 	{
  42. 		curB = curB->next;
  43. 		lenB++;
  44. 	}
  45. 	if (curA != curB)
  46. 	{
  47. 		return NULL;
  48. 	}
  49. 	struct ListNode* longList = headA, * shortList = headB;
  50. 	if (lenA < lenB)
  51. 	{
  52. 		longList = headB;
  53. 		shortList = headA;
  54. 	}
  55. 	//长的链表先走差距步
  56. 	int gap = abs(lenA - lenB);
  57. 	while (gap--)
  58. 	{
  59. 		longList = longList->next;
  60. 	}
  61. 	//同时走找交点
  62. 	while (longList != shortList)
  63. 	{
  64. 		longList = longList->next;
  65. 		shortList = shortList->next;
  66. 	}
  67. 	return longList;
  68. }
  69. struct ListNode* detectCycle(struct ListNode* head)
  70. {
  71. 	struct ListNode* slow = head;
  72. 	struct ListNode* fast = head;
  73. 	while (fast && fast->next)
  74. 	{
  75. 		slow = slow->next;
  76. 		fast = fast->next->next;
  77. 		if (slow == fast)
  78. 		{
  79. 			struct ListNode* meet = slow;
  80. 			struct ListNode* next = meet->next;
  81. 			meet->next = NULL;
  82. 			struct ListNode* entryNode = getIntersectionNode(head, next);
  83. 			meet->next = next;
  84. 			return entryNode;
  85. 		}
  86. 	}
  87. 	return NULL;
  88. }

11.复制带随机指针的链表

  1. //复制带随机指针的链表
  2. struct Node
  3. {
  4. 	int val;
  5. 	struct Node* next;
  6. 	struct Node* random;
  7. };
  8. struct Node* copyRandomList(struct Node* head)
  9. {
  10. 	//1.插入copy结点
  11. 	struct Node* cur = head;
  12. 	struct Node* copy = NULL;
  13. 	struct Node* next = NULL;
  14. 	while (cur)
  15. 	{
  16. 		next = cur->next;
  17. 		copy = (struct Node*)malloc(sizeof(struct Node));
  18. 		copy->val = cur->val;
  19. 		cur->next = copy;
  20. 		copy->next = next;
  21. 		cur = next;
  22. 	}
  23. 	//2.更新random
  24. 	cur = head;
  25. 	while (cur)
  26. 	{
  27. 		copy = cur->next;
  28. 		if (cur->random == NULL)
  29. 		{
  30. 			copy->random = NULL;
  31. 		}
  32. 		else
  33. 		{
  34. 			copy->random = cur->random->next;
  35. 		}
  36. 		cur = cur->next->next;
  37. 	}
  38. 	//3.copy结点要解下来链接在一起 恢复原链表
  39. 	struct Node* copyHead = NULL;
  40. 	struct Node* copyTail = NULL;
  41. 	cur = head;
  42. 	while (cur)
  43. 	{
  44. 		copy = cur->next;
  45. 		next = copy->next;
  46. 		if (copyTail == NULL)
  47. 		{
  48. 			copyHead = copyTail = copy;
  49. 		}
  50. 		else
  51. 		{
  52. 			copyTail->next = copy;
  53. 			copyTail = copyTail->next;
  54. 		}
  55. 		//恢复原链表链接
  56. 		cur->next = next;
  57. 		cur = next;
  58. 	}
  59. 	return copyHead;
  60. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/683300
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号