链表双指针问题_双指针跑步

让我们从一个经典问题开始：给定一个链表，判断链表中是否有环。

想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况：

• 如果没有环，快指针将停在链表的末尾。
• 如果有环，快指针最终将与慢指针相遇。

一般来说我们把快指针的速度设为2，慢指针设为1。

求环形链表的入环点

问题描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

首先必须认识到，快慢指针相遇的点并不一定是入环点。所以这时候我们需要第三个从头出发的指针，慢指针从相遇的出发，两个指针都以1的速度前进，最终的相遇点即为入环点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL) return NULL;
        ListNode *fast,*slow,*ring;
        fast=head;slow=head;ring=head;
        while(1)
        {
            if(fast==NULL)
            return NULL;
            else
            fast=fast->next;
            if(fast==NULL)
            return NULL;
            else
            fast=fast->next;
            slow=slow->next;
            if(slow==fast)
            break;
        }
        while(slow!=ring)
        {
            ring=ring->next;
            slow=slow->next;
        }
        return ring;
    }
};

 相交链表相交点

问题描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

所谓相交链表，将末尾和其中一头相连不就是环形链表吗？而且入环点也就是相交点。
所以与上题不同的的不过是先首尾相接，找到入环位置再把链表复原。

删除链表的倒数第N个节点

问题描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

这题如果不用双指针则需要遍历两次。

在链头创建双指针，快指针先走n步，然后双指针同速前进直至快指针到链尾，此时慢指针的下一个节点就是要删除的。删除后返回头结点就可以了。

但是有一个特例，就是n=链表的长度时，即快指针=null，需要删去是头结点而不是慢指针的下一个。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast,*slow;
        fast=head;slow=head;
        for(int i=0;i<n;i++)
        fast=fast->next;
        if(fast==NULL)
        return head->next;
        while(fast->next!=NULL)
        {
            fast=fast->next;
            slow=slow->next;
        }
        if(n==1)
        {
            slow->next=NULL;
        }
        else
        {
            fast=slow->next->next;
            slow->next=fast;
        }
        return head;
    }
};