一、 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
https://leetcode.cn/problems/merge-two-sorted-lists/
代码1展示：（不带头）
1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ 2. if (list1 == NULL) 3. { 4. return list2; 5. } 6. if (list2 == NULL) 7. { 8. return list1; 9. } 10. struct ListNode* head = NULL; 11. struct ListNode* tail = NULL; 12. while (list1 && list2) 13. { 14. struct ListNode* next1 = list1->next; 15. struct ListNode* next2 = list2->next; 16. if ((list1->val) < (list2->val)) 17. { 18. if (tail == NULL) 19. { 20. head = list1; 21. tail = list1; 22. } 23. else 24. { 25. tail->next = list1; 26. tail = list1; 27. } 28. list1 = next1; 29. } 30. else 31. { 32. if (tail == NULL) 33. { 34. head = list2; 35. tail = list2; 36. } 37. else 38. { 39. tail->next = list2; 40. tail = list2; 41. } 42. list2 = next2; 43. } 44. } 45. 46. if (list1 != NULL) 47. { 48. tail->next = list1; 49. 50. } 51. 52. if (list2 != NULL) 53. { 54. tail->next = list2; 55. } 56. return head; 57. }
思路：每次取小的节点尾插到新的节点
注意：其中一个为空的情况要注意
有头单链表：head->next指的是第一个节点的地址（带头，相当于开头多了一个节点，但是节点里面的val不确定，next指向下一个节点）； 无头单链表：head指的是第一个节点的地址； OJ题默认不带头
代码2展示：（带头）
1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. 9. 10. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ 11. struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头 12. struct ListNode* tail = head; 13. head->next = NULL;//就是含有值的节点的第一个 14. while (list1 && list2) 15. { 16. struct ListNode* next1 = list1->next; 17. struct ListNode* next2 = list2->next; 18. if ((list1->val) < (list2->val)) 19. { 20. tail->next = list1; 21. tail = list1; 22. list1 = next1; 23. } 24. else 25. { 26. tail->next = list2; 27. tail = list2; 28. list2 = next2; 29. } 30. } 31. 32. if (list1 != NULL) 33. { 34. tail->next = list1; 35. 36. } 37. if (list2 != NULL) 38. { 39. tail->next = list2; 40. } 41. struct ListNode* list = head->next; 42. free(head); 43. return list; 44. }
思路：每次取小的节点尾插到新的节点
注意：mallloc的一个地址，到最后要进行释放。
二、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
代码展示：
1. /* 2. struct ListNode { 3. int val; 4. struct ListNode *next; 5. ListNode(int x) : val(x), next(NULL) {} 6. };*/ 7. class Partition { 8. public: 9. ListNode* partition(ListNode* pHead, int x) { 10. // write code here 11. struct ListNode* LessHead = (struct ListNode*)malloc(sizeof(struct ListNode)); 12. struct ListNode* LessTail = LessHead; 13. struct ListNode* GreaterHead = (struct ListNode*)malloc(sizeof(struct ListNode)); 14. struct ListNode* GreaterTail = GreaterHead; 15. struct ListNode* cur = pHead; 16. while (cur != NULL) 17. { 18. if (cur->val < x) 19. { 20. LessTail->next = cur; 21. LessTail = cur; 22. } 23. else 24. { 25. GreaterTail->next = cur; 26. GreaterTail = cur; 27. } 28. cur = cur->next; 29. } 30. GreaterTail->next = NULL; 31. LessTail->next = GreaterHead->next; 32. struct ListNode* list = LessHead->next; 33. free(LessHead); 34. free(GreaterHead); 35. return list; 36. 37. 38. } 39. };
思路：小于x的插入到一个链表，大于等于x的插入到一个链表，链表1和链表2合并（用带头的）
注意：链表2的最后一项要指向NULL，如果不指向NULL，就可能造成死循环【链表的题，要注意头和尾】
三、 链表的回文结构
代码展示：
1. /* 2. struct ListNode { 3. int val; 4. struct ListNode *next; 5. ListNode(int x) : val(x), next(NULL) {} 6. };*/ 7. 8. struct ListNode* reverseList(struct ListNode* head){ 9. struct ListNode* cur = head; 10. struct ListNode* prev = NULL; 11. while(cur) 12. { 13. struct ListNode* next = cur->next; 14. cur ->next = prev; 15. prev = cur; 16. cur = next; 17. } 18. return prev; 19. } 20. 21. struct ListNode* middleNode(struct ListNode* head) 22. { 23. struct ListNode* slow = head; 24. struct ListNode* fast = head; 25. while (fast && (fast ->next)) 26. { 27. slow = slow ->next; 28. fast = fast->next->next; 29. } 30. return slow; 31. } 32. 33. class PalindromeList { 34. public: 35. bool chkPalindrome(ListNode* A) { 36. // write code here 37. struct ListNode* mid = middleNode(A); 38. struct ListNode* rHead = reverseList(mid); 39. while (A && rHead) 40. { 41. if (A->val == rHead->val) 42. { 43. A = A->next; 44. rHead = rHead->next; 45. } 46. else 47. { 48. return false; 49. } 50. } 51. return true; 52. } 53. };
思路：首先找到链表的中间的地址（奇数个）或者是中间的第二个地址（偶数个）作为第二个链表的头，然后逆置第二个链表，然后第原始链表和第二个链表进行比较。（当原始链表和第二个链表有一个是空的时候，就可以跳出循环，说明是回文链表
四、 输入两个链表，找出它们的第一个公共结点
https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
代码展示：（思路2）
1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 9. { 10. //判断是否相交 11. struct ListNode* tailA = headA; 12. struct ListNode* tailB = headB; 13. int lenA = 1; 14. int lenB = 1; 15. while (tailA->next != NULL) 16. { 17. tailA = tailA->next; 18. lenA++; 19. } 20. while (tailB->next != NULL) 21. { 22. tailB = tailB->next; 23. lenB++; 24. } 25. if (tailA != tailB) 26. { 27. return NULL; 28. } 29. //找到节点 30. int gap = abs(lenA - lenB); 31. //想法值得学习，大小 32. struct ListNode* shortList = headA; 33. struct ListNode* longList = headB; 34. if (lenA > lenB) 35. { 36. shortList = headB; 37. longList = headA; 38. } 39. while(gap--) 40. { 41. longList = longList->next; 42. } 43. while (longList && shortList) 44. { 45. if (longList == shortList) 46. { 47. return longList; 48. } 49. longList = longList->next; 50. shortList = shortList->next; 51. } 52. return NULL; 53. }
思路1：A链表每一个节点和B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。
（判断是否是相交，交点是多少）时间复杂度：O(M*N)
思路2：当尾节点的地址相同的时候，就是相交。（判断是否是相交）
求出两个链表的长度，然后链表长的先走两个链表的差值，然后两个链表一起走，当地址相同的时候，位置就是节点（交点是多少）时间复杂度：O(M+N)
注意：（1）地址相同，不是值相等（值相等不一定是节点）
（2）编译器执行的是语法错误，编译器不能检查出执行逻辑，所以在最后要加上return NULL（因为上面有一个if之后返回一个值，编译器会认为不满足这个if条件的时候没有返回值）;
五、 给定一个链表，判断链表中是否有环
https://leetcode.cn/problems/linked-list-cycle/submissions/
代码展示：
1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. bool hasCycle(struct ListNode *head) 9. { 10. struct ListNode* slow = head; 11. struct ListNode* fast = head; 12. while (fast && fast->next) 13. { 14. fast = fast->next->next; 15. slow = slow->next; 16. if (fast == slow) 17. { 18. return true; 19. } 20. } 21. return false; 22. }
思路：[快慢指针]slow一次走一步，fast一次走两步，当slow进环之后，开启追赶模式，最后fast追上slow；不带环fast->next或者fast就会是NULL，带环的话就不会是NULL；
注意：刚开始fast等于slow，所以再循环里面先赋值，后比较
（1）slow一次走一步,fast一次走两步，一定能追上。
当slow走一半的时候，fast开始进环。此时两者的距离为N，每次之后，距离会减少1，所以就一定能追上。【距离为0，追上】
（2）slow一次走一步,fast一次走三步，不一定能追上。
当slow走1/3的时候，fast开始进环。此时两者的距离为N，每次之后，距离会减少2，如果距离为奇数，就会错过，【偶数可以追上】，此时距离又为环数-1【偶数追上，奇数就永远追不上】，所以不一定能追上。
六、 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
https://leetcode.cn/problems/linked-list-cycle-ii/description/
代码展示：(思路一）
1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. struct ListNode *detectCycle(struct ListNode *head) 9. { 10. struct ListNode* fast = head; 11. struct ListNode* slow = head; 12. while (fast && fast->next) 13. { 14. fast = fast->next->next; 15. slow = slow->next; 16. if (fast == slow) 17. { 18. struct ListNode* meet = slow; 19. while (head != meet) 20. { 21. meet = meet->next; 22. head = head->next; 23. } 24. return meet; 25. } 26. } 27. return NULL; 28. }
思路1：假设，进入环之前的距离为L；slow两者相遇后之前，进入环之后走的距离x；进入环之后两者的距离为N ；环的长度为C [快慢指针]slow一次走一步，fast一次走两步，fast是slow的两倍【slow绝对不会走一圈被fast追上，而是没有走一圈就被fast给追上了，因为当slow进入环之后，两者的距离为N，N肯定小于环数，所以两者相遇的时候，slow肯定没有走完一圈，所以slow走得距离为进入环之前的距离L+两者相遇后之前，进入环之后走的距离x即L+x;fast走的距离为nC+L+x; n*C+L+x=2(L+x),----n*C=L+x;n为未知数】【slow进环之后，fast不可能走完一圈】n*C=L+x:能证明，一个从进入链表走，一个从相遇的那个节点走，slow和fast在环入口处相遇。
思路2：转换成求链表交点。【从相遇处开始断开】meet作为尾，meet->next作为头 ，head给出，求交点。
七、 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深度拷贝
https://leetcode.cn/problems/copy-list-with-random-pointer/description/
代码展示：
1. /** 2. * Definition for a Node. 3. * struct Node { 4. * int val; 5. * struct Node *next; 6. * struct Node *random; 7. * }; 8. */ 9. 10. struct Node* copyRandomList(struct Node* head) 11. { 12. struct Node* cur = head; 13. //拷贝节点链接 14. while (cur!= NULL) 15. { 16. struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); 17. copy->val = cur->val; 18. copy->next = cur->next; 19. cur->next = copy; 20. cur = cur->next->next; 21. } 22. //random 23. cur = head; 24. while (cur != NULL) 25. { 26. if (cur->random == NULL) 27. { 28. cur->next->random = NULL; 29. } 30. else 31. { 32. cur->next->random = cur->random->next; 33. } 34. cur = cur->next->next; 35. } 36. //摘下来、链接 37. struct Node* copyHead = NULL; 38. struct Node* copyTail = NULL; 39. cur = head; 40. while (cur != NULL) 41. { 42. struct Node* copy = cur->next; 43. struct Node* next = copy->next; 44. if (copyHead == NULL) 45. { 46. copyHead = copyTail = copy; 47. } 48. else 49. { 50. copyTail->next = copy; 51. copyTail = copy; 52. } 53. cur = next; 54. } 55. return copyHead; 56. 57. }
思路：拷贝每一个节点连接在原节点之后，链接拷贝节点的random，新的random在前面的random的next。最后，把拷贝节点解下来，链接起来。【索引从0开始】
