【编织时空三：探究顺序表与链表的数据之旅】（上）：https://developer.aliyun.com/article/1424876
思路二：哨兵位法，创建一个带头结点的链表，尾插的时候就不需要判断链表是不是为空的尾插情况，最后再释放哨兵位即可。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL) return list2; if (list2 == NULL) return list1; struct ListNode* newhead = NULL; struct ListNode* tail = NULL; //哨兵位，方便尾插 newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); while (list1 && list2) { //小值给到新链表上 if (list1->val < list2->val) { tail->next = list1; tail = tail->next; list1 = list1->next; } else { tail->next = list2; tail = tail->next; list2 = list2->next; } } if (list1) tail->next = list1; if (list2) tail->next = list2; struct ListNode* del = newhead; newhead = newhead->next; //释放哨兵位 free(del); return newhead; }
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接
思路：首先创建四个节点lessHead,greaterHead,lessTail,greaterTail ，遍历整个链表，比x小的尾插到lessHead为哨兵位的那个链表，比x大的尾插到greaterHead为哨兵位的那个链表，再把两个链表连接起来 ，创建一个list节点指向这个链表 ，把greaterTail->next置空，避免成环 ，释放lessHead,greaterHead，返回list
struct ListNode* partition(struct ListNode* pHead, int x) { struct ListNode* lessHead, * greaterHead; lessHead = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* lessTail = lessHead; struct ListNode* greaterTail = greaterHead; struct ListNode* cur = pHead; while (cur) { if (cur->val < x) { lessTail->next = cur; lessTail = lessTail->next; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } lessTail->next = greaterHead->next; //此时greaterTail->next仍然链接初始链表的结点，需要置空，否则连环 greaterTail->next = NULL; struct ListNode* newhead = lessHead->next; free(lessHead); free(greaterHead); return newhead; }
7. 链表的回文结构。OJ链接
思路：先找到链表的中间结点，再把中间结点之后的逆序，和之前的链表比较值是否相等。
struct ListNode* middleNode(struct ListNode* head)//找中间结点 { struct ListNode* fast = head; struct ListNode* slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head)//反转链表 { struct ListNode* cur = head; struct ListNode* newhead = NULL; while (cur) { //保存cur下一个结点的位置 struct ListNode* next = cur->next; //头插 next = newhead; newhead = cur; //更新 cur = next; } return newhead; } bool chkPalindrome(struct ListNode* A) //查看值是否相等 { struct ListNode* midnode = middleNode(A); struct ListNode* reversemidnode = reverseList(midnode); while (A && reversemidnode) { if(A->val != reversemidnode->val) { return false; } A = A->next; reversemidnode = reversemidnode->next; } return true; }
8. 输入两个链表，找出它们的第一个公共结点。OJ链接
思路：先计算两个链表的长度，再让较长的链表走差距步abs(lenA-LenB)长度，然后再依次比较是否相等。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { struct ListNode* curA = headA, * curB = headB; //找尾结点 - 结点总数会少一个 int lenA = 1;//设置为1 int lenB = 1;//设置为1 while (curA->next) { curA = curA->next; lenA++; } while (curB->next) { curB = curB->next; lenB++; } //两个链表不相交 if (curA != curB) return NULL; //找长链表 struct ListNode* LongList = headA, * ShortList = headB; if (lenA < lenB) { LongList = headB; ShortList = headA; } //长链表走绝对值（lenA - lenB）步 int count = abs(lenA - lenB); while (count--) { LongList = LongList->next; } //同时向后走，相同就停下来 while (LongList != ShortList) { LongList = LongList->next; ShortList = ShortList->next; } return ShortList; }
9. 给定一个链表，判断链表中是否有环。OJ链接
思路：快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行， 如果链表 环则一定会在环中相遇，否则快指针率先走到链表的末尾。
bool hasCycle(struct ListNode *head) { struct ListNode* fast = head ,* slow = head; while(fast && fast->next) { fast = fast->next; slow = slow->next->next; if(fast == slow) return true; } return false; }
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚 进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，快指针走两次，慢指针走一次，之间的距离就缩小一步，直至最后差距为0，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，...n步行吗？
10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL。OJ链接
思路一：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast = head,*slow = head; while(fast && fast->next) { slow = slow->next; fast = fase->next->next; //相遇在环内任意一个位置 if(slow == fast) { struct ListNode *meet = slow; //两结点关系L = (N-1) * C + C - X; while(head != meet) { head = head->next; meet = meet->next; } return meet; } } return NULL; }
思路二：两个指针相遇的地方的下一个结点置空，下一个结点位置和链表头指针此时就可以转为两条链表求解公共点的问题。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)//相交点 { struct ListNode* curA = headA, * curB = headB; //找尾结点 - 结点总数会少一个 int lenA = 1;//设置为1 int lenB = 1;//设置为1 while (curA->next) { curA = curA->next; lenA++; } while (curB->next) { curB = curB->next; lenB++; } //两个链表不相交 if (curA != curB) return NULL; //找长链表 struct ListNode* LongList = headA, * ShortList = headB; if (lenA < lenB) { LongList = headB; ShortList = headA; } //长链表走绝对值（lenA - lenB）步 int count = abs(lenA - lenB); while (count--) { LongList = LongList->next; } //同时向后走，相同就停下来 while (LongList != ShortList) { LongList = LongList->next; ShortList = ShortList->next; } return ShortList; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast = head,*slow = head; while(fast && fast->next) { slow = slow->next; fast = fase->next->next; //相遇在环内任意一个位置 if(slow == fast) { struct ListNode *meet = slow; struct ListNode *newhead = meet->next; meet->next = NULL; return getIntersectionNode(head,newhead); } } return NULL; }
11.给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。 要求返回这个链表的深度拷贝。OJ链接
思路：迭代 + 节点拆分
方法：
struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; while(cur) { struct Node* next = cur->next; struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //插入 cur->next = copy; copy->next = next; //往后走 cur = next; } cur = head; while(cur) { struct Node* copy = cur->next; //置 copy random if(cur->random == NULL) copy->random = NULL; else copy->random = cur->random->next; cur = copy->next; } cur = head; struct Node* copyhead = NULL,*cpoytail = NULL; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; //copy结点尾插到新链表 if(cpoytail == NULL) { copyhead = copytail = copy; } else { copytail->next = copy; copytail = copytail->next; } //恢复原链表 cur->next = next; cur = next; } return copyhead; }
