一、删除链表的倒数第N个节点
题目：19. Remove Nth Node From End of List
分析：典型的利用双指针法解题。首先让指针first指向头节点，然后让其向后移动n步，接着让指针sec指向头结点，并和first一起向后移动。当first的next指针为NULL时，sec即指向了要删除节点的前一个节点，接着让first指向的next指针指向要删除节点的下一个节点即可。注意如果要删除的节点是首节点，那么first向后移动结束时会为NULL，这样加一个判断其是否为NULL的条件，若为NULL则返回头结点的next指针。
解法一：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode* first = head;
while(n--)
first = first->next;
if(!first)
return head->next;
ListNode* sec = head;
while(first->next)
{
sec = sec->next;
first = first->next;
}
sec->next = sec->next->next;
return head;
}
};二、相交链表
题目：160. Intersection of Two Linked Lists
解法一：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//这个思路就是 ListA + ListB = A + intersection + Bb + intersection
//ListB + ListA = Bb + intersection + A + intersection
//用大A表示ListA里面非共有 Bb表示listB里面非共有的，可以看到在第二个intersection的开头两个链表长度是一样的，必然相等
//所以我们可以遍历A再遍历B，另一个遍历B再遍历A，两个指针必定在第二个交集处相遇，没有交集就是空指针
ListNode *cursorA = headA;
ListNode *cursorB = headB;
if (!cursorA || !cursorB)
return NULL;
while (cursorA != cursorB)
{
if (!cursorA)
cursorA = headB;
else
cursorA = cursorA->next;
if (!cursorB)
cursorB = headA;
else
cursorB = cursorB->next;
}
return cursorA;
}
};三、环形链表
解法一：
class Solution {
public:
bool hasCycle(ListNode *head)
{
ListNode *slow = head, *fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};四、环形链表 II
如下图所示，X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：
2*(a + b) = a + b + n * (b + c)；即：a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
注意到b+c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。故两指针会在环开始位置相遇。
解法一：
class Solution {
public:
ListNode *detectCycle(ListNode *head)
{
if (head == NULL || head->next == NULL)
return NULL;
ListNode * p = head;
ListNode * q = head;
while (q != NULL && q->next != NULL)//第一次pq相遇
{
p = p->next;
q = q->next->next;
if (p == q) break;
}
if (p == q)
{
p = head;
while (p != q)//从起点开始，在入口点相遇
{
p = p->next;
q = q->next;
}
return p;
}
return NULL;
}
};