链表

6. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

思路：
用双指针的方法，fast 和 slow 之间保持距离为 n，只需要遍历一次即可完成删除任务。
为了方便删除头节点，设置一个虚拟指针。

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (head == NULL || head->next == NULL) return NULL;ListNode *_dummyHead = new ListNode(0);_dummyHead->next = head;ListNode *fast = _dummyHead;ListNode *slow = _dummyHead;while (n--) {fast = fast->next;}while (fast->next) {fast = fast->next;slow = slow->next;}ListNode *tmp = slow->next;slow->next = slow->next->next;delete tmp;return _dummyHead->next;}
};

7. 链表相交

面试题 02.07. 链表相交

思路：
分别计算出两链表的长度，然后让较长的链表头指针移动到剩余节点数和较短的链表一样长；
然后两头指针同时移动，直到两指针相同，则找到答案。否则没有交点返回 NULL。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *curA = headA;ListNode *curB = headB;int lenA = 0, lenB = 0;int delta = 0;while (curA) {curA = curA->next;lenA++;}while (curB) {curB = curB->next;lenB++;}if (lenA >= lenB) {delta = lenA - lenB;} else {delta = lenB - lenA;swap(headA, headB);}while (delta--) {headA = headA->next;}while (headA) {if (headA == headB) return headA;headA = headA->next;headB = headB->next;}return NULL;}
};

8. 环形链表 II

142. 环形链表 II

思路：
将链表按如下方式划分：

用快慢两个指针从起点出发，fast 每次走 2，slow 每次走 1，如果有环则 fast 和 slow 一定会在环中相遇，如果 x 很长的话，此时 fast 有可能已经在环中转悠好几圈了(n圈)，由 slow 走过的路 (x+y) 和 fast 走过的路 (x+y+n*(z+y)) 可以得到如下等式
$(x+y)\ast 2=x+y+n\ast (y+z)$
即 $x=(n-1)\ast (y+z)+z$
可见，x 等于走完 z 在走几圈环，所以，两个节点分别从起点和 fast、slow 相交处出发，每次走 1，一定会在环形入口处第一次相交。

class Solution {
public:ListNode *detectCycle(ListNode *head) {if (head == NULL || head->next == NULL) return NULL;ListNode *cur1 = head->next;ListNode *cur2 = head->next->next;while (cur1 && cur2 && cur2->next && cur2 != cur1) {cur1 = cur1->next;cur2 = cur2->next->next;}if (cur1 != cur2) return NULL;cur1 = head;while (cur1 != cur2) {cur1 = cur1->next;cur2 = cur2->next;}return cur1;}
};