判断链表是否有环

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        
        while (fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
};

使用快慢指针，如果有环，快慢指针会相遇。有人疑惑，快指针每次走两步，慢指针每次走一步，有没有可能，每次快指针都跳过了慢指针。不会，每次都会相遇，原因如下：

慢指针每次移动一格，快指针每次移动两格，在有环的链表里，他们一定会相遇

1. 当快指针就在慢指针后面，那么下一次慢指针移动一位，快指针移动两位，相遇
2. 当快指针和慢指针差一个位置，那么下一次慢指针移动一位，快指针移动两位，他们会变成第一种情况
3. 当快指针和慢指针差两个位置，那么下一次慢指针移动一位，快指针移动两位，他们会变成第二种情况

————————————————
版权声明：本文为CSDN博主「Leslie5205912」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Leslie5205912/article/details/89386769

判断两个链表是否相交

为了找到交点，可以先得出两个链表的长度。算出它们的长度差异 N，让长链表的指针先走 N 步，然后两个链表的指针齐头并进。如果两个链表相交，这两个指针就一定会相遇，否则都会各自走到链表尾部。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return NULL;
        int lenA = len(headA);
        int lenB = len(headB);

        if(lenA > lenB){
            headA = advance(headA, lenA-lenB);
        }else{
            headB = advance(headB, lenB-lenA);
        }
        while(headA && headA != headB){
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }

    int len(ListNode *head){
        int n = 0;
        while(head->next){
            n++;
            head = head->next;
        }
        return n;
    }

    ListNode* advance(ListNode *head, int n){
        while(n > 0){
            head = head->next;
            n--;
        }
        return head;
    }
};

另外一种思路，很巧妙。设两个链表非公共部分的长度为 a b 设公共部分的长度为 c。如果将 A 和 B 链表后面各自接上另外一个链表。那么这两个链表的长度就一样了，即 a+b+c+c。如果两个链表相交，那么交点一定在倒数第 c 个节点上。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || !headB) return NULL;
    ListNode *pA = headA, *pB = headB;
    while(pA != pB){
        pA = (pA == NULL) ? headB : pA->next;
        pB = (pB == NULL) ? headA : pB->next;
    }
    return pA;
}

判断链表环的入口

如果一个链表有环，那么找出环的入口。这个问题组合前面两步的思路来解决。如果链表有环，那么我们得到环内的某个节点，然后从该节点断开。这样就变成了找两个链表的交点的问题了。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *head1 = head;
        ListNode *node_in_cycle = findOneNodeInCycle(head);
        if(!node_in_cycle){
            return NULL;
        }
        ListNode *head2 = node_in_cycle->next;

        ListNode *p1 = head1, *p2 = head2;
        while(p1 != p2){
            p1 = p1->next;
            p2 = (p2 == node_in_cycle) ? head1 : p2->next;
        }
        return p1;
    }


    ListNode* findOneNodeInCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;

        while (fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                return fast;
            }
        }
        return NULL;
    }
};

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(!pListHead) return NULL;

        ListNode *first = pListHead, *second = pListHead;
        for(int i=0; i < k; ++i){
            if(!first) return NULL;
            first = first->next;
        }
        while(first){
            first = first->next;
            second = second->next;
        }
        return second;
    }
};

用两个指针，第一个先走 k 步，然后两个指针一起向前走。当前一个达到终点的时候，第二个恰好是倒数第 k 个节点。

反转链表

输入一个链表，反转链表后，输出新链表的表头。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        ListNode *p = NULL;
        while(head){
            ListNode *next = head->next;
            head->next = p;
            p = head;
            head = next;
        }
        return p;
    }
};

不断把后一个节点，作为头结点，即可反转链表。