7.链表的回文结构 OJ链接
分析：判断链表是否是回文结构，可以结合前面的题：
（1）利用快慢指针找到链表中间结点
（2）将后半部分逆置
（3）将（2）中的链表从第一个节点开始和中间结点开始同时进行访问，如果所有val相等，则链表为回文结构。
1. struct ListNode { 2. int val; 3. struct ListNode *next; 4. ListNode(int x) : val(x), next(NULL) {} 5. }; 6. 7. struct ListNode* middleNode(struct ListNode* head) 8. { 9. // write code here 10. struct ListNode* slow = head; 11. struct ListNode* fast = head; 12. 13. while(fast && fast->next) 14. { 15. slow = slow->next; 16. fast = fast->next->next; 17. } 18. 19. return slow; 20. 21. } 22. 23. struct ListNode* reverseList(struct ListNode* head) 24. { 25. struct ListNode* cur = head; 26. struct ListNode* newHead = NULL; 27. 28. while(cur) 29. { 30. struct ListNode* next = cur->next; 31. 32. cur->next = newHead; 33. newHead = cur; 34. cur = next; 35. } 36. return newHead; 37. } 38. 39. bool chkPalindrome(ListNode* A) 40. { 41. struct ListNode* mid = middleNode(A); 42. struct ListNode* rHead = reverseList(mid); 43. 44. while(A && rHead) 45. { 46. if(A->val != rHead->val) 47. { 48. return false; 49. } 50. else 51. { 52. A = A->next; 53. rHead = rHead -> next; 54. } 55. } 56. 57. return true; 58. }
8.输入两个链表，找出它们的第一个公共结点 OJ链表
分析：判断链表是否相交，是判断是否有两个节点地址相同，而不是判断是否有两个结点值相同。
（1）若只是判断两个链表是否相交，直接判断最后一个链表是否相等即可
（2）要找出相交的结点：
a.计算两个链表的长度，计算两个链表的长度差距
b.让长链表先走差距步，再让两个链表同时向前走，若有相同的结点即相交。
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. if(headA == NULL || headB == NULL) 11. { 12. return NULL; 13. } 14. 15. struct ListNode *curA = headA, *curB = headB; 16. 17. int lenA = 0,lenB = 0; 18. 19. while(curA->next) 20. { 21. curA = curA->next; 22. lenA++; 23. } 24. 25. while(curB->next) 26. { 27. curB = curB->next; 28. lenB++; 29. } 30. 31. if(curA != curB) 32. { 33. return NULL; 34. } 35. 36. struct ListNode *longList = headA,*shortList = headB; 37. if(lenA < lenB) 38. { 39. longList = headB; 40. shortList = headA; 41. } 42. 43. int gap = abs(lenA - lenB); 44. while(gap--) 45. { 46. longList = longList->next; 47. } 48. 49. while(longList != shortList) 50. { 51. longList = longList->next; 52. shortList = shortList->next; 53. } 54. 55. return longList; 56. }
9.给定一个链表，判断链表中是否有环 OJ链接
分析：
如何判断链表是否有环：使用快慢指针，慢指针一次走1步，快指针一次走2步，如果链表带环，那么快慢同时从链表起始位置开始向后走，一定会在环内相遇，此时快慢指针都有可能在环内打圈，直到相遇；否则，如果链表不带环，那么快指针会先走到链表末尾，慢指针只能在链表末尾追上快指针。
1. struct ListNode { 2. int val; 3. struct ListNode *next; 4. }; 5. 6. bool hasCycle(struct ListNode *head) 7. { 8. struct ListNode *slow = head; 9. struct ListNode *fast = head; 10. 11. while(fast && fast->next) 12. { 13. slow = slow->next; 14. fast = fast->next->next; 15. 16. if(slow == fast) 17. { 18. return true; 19. } 20. } 21. 22. return false; 23. 24. }
如果快指针不是一次走2步，而是一次走3步，一次走4步一次走x步呢？能不能判断出链表是否带环呢？
如果快指针一次走两步，当slow从直线中间移动到直线末尾时，fast又走了slow的2倍，因此当slow进环时，fast可能在环的任意位置，具体要看直线有多长，环有多大。在环内，一定是fast追slow，因为fast比slow移动的快。
fast一次走3步：假设slow进环的时候，fast跟slow相差N步，环的长度为C，追击时，slow走1步，fast走3步，每走1次，差距就缩小2，如下图所示：
因此对于N，如果N为奇数，一定不会相遇 ，差距为：N,N-2,N-4,···,1,-1(-1即C-1，一直是fast在追slow)
如果N为奇数，一定会相遇 ，差距为：N,N-2,N-4,···,2,0
那么根据以上推论，如果fast一次走4步， 如果N为奇数，差距为：N,N-3,N-6,···,4,1,-2， 如果N为奇数，差距为：N,N-3,N-6,···,5,2,-1
总结：如果slow进环时，slow和fast的差距N是奇数，且环的长度C为偶数(则C-1为奇数，上面举例可以看出差距最小为1或-1)，那么就永远追不上了。
10.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL OJ链接
如何求环的入口点？假设起点到入口点的距离是L，假设相遇点到入口点的距离是X，假设环的大小是C，相遇时，快指针已经在环内打转了N圈，那么慢指针走的路程为L+X，快指针走的路程为L+N*C+X，则有以下公式恒成立：
根据以上公式，则有L=N*C-X。因此，如果让快指针从相遇点出发，慢指针从起点出发，它们会在入口点相遇，此时快指针已经在圈内打转了N圈，快指针走的路程为N*C-X，慢指针走的路程为L。
1. struct ListNode { 2. int val; 3. struct ListNode *next; 4. }; 5. 6. struct ListNode* detectCycle(struct ListNode* head) 7. { 8. struct ListNode* slow = head; 9. struct ListNode* fast = head; 10. 11. while (fast && fast->next) 12. { 13. slow = slow->next; 14. fast = fast->next->next; 15. 16. if (slow == fast) 17. { 18. struct ListNode* meet = fast; 19. 20. while (meet != head) 21. { 22. meet = meet->next; 23. head = head->next; 24. } 25. 26. return meet; 27. } 28. } 29. 30. return NULL; 31. }
11.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。OJ链接
（1）next如何处理?直接将结点拷贝下来是有问题的，把7拷贝下来指向的还是原来的13，而不是新创建的结点13，虽然值都是13，但是地址却不同。
所以要malloc之后，把值拷贝出来，然后把拷贝结点7的next指向原结点13。
（2）拷贝节点的random如何处理？如果直接处理，效率太低
a.拷贝以后，新链表需要确定每个random，需要去链表中查找，时间复杂度是O(N)，每个random都要处理就是O(N*N)，效率低
b.如果链表中存在节点的值相同，那么就更复杂了，比如有多个节点的值是7，那么原链表random有几个指向7的节点呢？新链表的random分别对应哪个7呢？毕竟各个7的地址不同。
把拷贝结点链接在原结点的后面，当找到原结点13的random结点7就能找到原结点7的拷贝结点，因为拷贝结点就是链接在原结点的后面，原结点13的random指向原结点7，拷贝结点13的random指向拷贝结点7。拷贝结点的random等于原结点random的next，即找到原结点就找到拷贝结点了。
（3）不能先让原结点7指向拷贝7，否则原结点7找不到原结点13了，应该让原结点7的copy结点7指向原结点7的next结点13。
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. if (head == NULL) 13. { 14. return NULL; 15. } 16. 17. //1.将拷贝结点挂在原结点后面，建立对应关系 18. struct Node* cur = head; 19. 20. while (cur) 21. { 22. 23. struct Node* next = cur->next; 24. struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); 25. copy->val = cur->val; 26. cur->next = copy; 27. copy->next = next; 28. cur = next; 29. 30. } 31. 32. //2.处理copy结点的random 33. cur = head; 34. while (cur) 35. { 36. struct Node* copy = cur->next; 37. if (cur->random == NULL) 38. { 39. copy->random = NULL; 40. } 41. else 42. { 43. copy->random = cur->random->next; 44. } 45. cur = copy->next; 46. 47. } 48. 49. //3.将拷贝结点取下来链接到一起，恢复原链表 50. cur = head; 51. 52. struct Node* copyHead, * copyTail; 53. copyHead = copyTail = (struct Node*)malloc(sizeof(struct Node)); 54. 55. while (cur) 56. { 57. struct Node* copy = cur->next; 58. struct Node* next = copy->next; 59. 60. //尾插 61. copyTail->next = copy; 62. copyTail = copyTail->next; 63. cur = next; 64. } 65. 66. struct Node* guard = copyHead; 67. 68. copyHead = copyHead->next; 69. free(guard); 70. 71. return copyHead; 72. }
12.链表的插入排序 OJ链接
1. /** 2. * Definition for singly-linked list. 3. * struct ListNode { 4. * int val; 5. * struct ListNode *next; 6. * }; 7. */ 8. 9. 10. struct ListNode* insertionSortList(struct ListNode* head) 11. { 12. //1.初始条件 13. struct ListNode* sortHead = head; 14. struct ListNode* cur = head->next; 15. sortHead->next = NULL; 16. 17. while(cur)//2.终止条件 18. { 19. //3.迭代条件 20. struct ListNode* next = cur->next; 21. 22. //将cur结点插入到前面有序区间 23. struct ListNode* p = NULL, * c = sortHead; 24. while(c) 25. { 26. if(cur->val < c->val) 27. { 28. break; 29. } 30. else 31. { 32. p = c; 33. c = c->next; 34. } 35. } 36. 37. if(p == NULL) 38. { 39. 40. cur->next = c; 41. sortHead = cur; 42. } 43. else 44. { 45. p->next = cur; 46. cur->next = c; 47. } 48. 49. cur = next; 50. } 51. return sortHead; 52. }
顺序表和链表优缺点对比
| 顺序表 | 链表 | |
| 优点 | 1.按下标随机访问 2.CPU高速缓存命中率高 |
1.按需申请内存，不存在空间浪费 2.任意位置O(1)时间内插入删除数据 |
| 缺点 | 1.空间不够需增容（性能消耗及空间浪费） 2.头部或中间插入删除数据，需要挪动数据，效率低，时间复杂度O(n) |
1.不支持下标随机访问 2.访问数据需要遍历，时间复杂度O(N) |
顺序表和链表是相辅相成的，互相弥补对方的缺点，需要用顺序表还是链表存储数据，具体是看场景。
