我们专门开个链表的算法题坑，方便总结在笔面试中可能会涉及到的链表操作。

在ACM中我们都用数组模拟双向链表，所以就不要嘲笑为什么我一个ACMer还要整理力扣的题了，是真不会啊。

Easy

求两个单向链表的相交点

力扣链接

一般链表的题，输入只给你一个指向链表头的头指针。但是这题我们要求两个单向链表的相交点，所以我们开始有两个头指针 headA 和 headB。

怎么求相交点呢？或许可以枚举第一个链表上的每个点，然后遍历第二个链表的每个点，看看二者是否有相同的地址。这种显然是 O(n2) 的。

有没有更简单的解法呢？假设我们目标是想出一个 O(n) 的解法，那么似乎我们遍历一次链表就 O(n) 了。

遍历完了然后呢？假设我们此时从另一个链表重新开始遍历，会发生什么？

假设链表A和链表B有共同后缀长度 z，而A的前缀长度为 x，B为 y，那么我们同时从头遍历链表 A 和 B，若到头了就从另一个链表重新开始遍历。

那么你会惊讶地发现，当我们这么遍历 x + y + z 步后，二者所在的点就是交互点！

也就是说，如果我们直接按照“遍历完当前链表就换链表遍历”的想法遍历，就一定会在某个时刻，二者会到一个点上，而这个点就是我们要的相交点。

而且我们必然在第二次换链表遍历（即换回来原来链表开始遍历）之前得到该相交点。如果没有的话，说明二者无相交。

1
2
3
4
5
6
7
8
9
10
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* A{headA};
    ListNode* B{headB};
    while(A != B)
    {
        A = A ? A->next : headB;
        B = B ? B->next : headA;
    }
    return A;
}

反转链表

力扣链接

这个很简单，我们在遍历的时候改一改指针就行了。记录当前指针 p 和当前指针下一位 q，将 q 的指针指向 p 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* reverseList(ListNode* head) {
    if(!head) return head;
    ListNode* p{head};
    ListNode* q{head->next};
    while(q)
    {
        ListNode* tmp{q->next};
        q->next = p;
        p = q;
        q = tmp;
    }
    head->next = nullptr;
    return p;
}

判断一个链表是否是回文的

力扣链接

简单，直接把值记到一个数组内然后判回文

时间复杂度显然限制死 O(n)了，空间能不能优化成常数呢？

可以打破原有链表的结构。我们考虑获得链表的中间节点，然后将中间节点后续的链表进行反转。然后从两头进行遍历，这样的话就能达到常数空间了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isPalindrome(ListNode* head) {
    ListNode* slow{head};
    ListNode* fast{head};
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* q = reverseList(slow);
    bool pd{true};
    ListNode* p{head};
    while(p && q && pd)
    {
        if(p->val != q->val)
        {
            pd = false;
            break;
        }
        p = p->next;
        q = q->next;
    }
    return pd;
}

环形链表

力扣链接

判断链表是否有环。

同样用快慢节点。很容易可以算出，如果有环，那么在经过了环的长度的时间（实际上这是上界，可能也是环的长度除以二、除以三等等）后，二者会相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool hasCycle(ListNode *head) {
    if(!head) return false;
    ListNode* slow{head};
    ListNode* fast{head};
    bool pd{};
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            pd = true;
            break;
        }
    }
    return pd;
}

环形链表找第一个节点

力扣链接

上个题的升级版，在判断有无环的基础上要求找第一个节点。

上个题我们知道，slow节点第一次进入环内会和fast在环内旋转若干遍发生第一次接触。

假设用时 t 步，fast旋转了 k 遍，环前长度 x ，第一次接触到环前长度为 y，剩余长度为 z，那么可以分别得出slow节点和fast节点经过的距离。slow走了 t = x + y，fast走了 2t = x + k(y + z) + y，可以算出 x = (k − 1)y + kz。

也就是说 x 等于走了 k − 1 遍环加上 z，而slow节点在环的第 y 个节点相遇，如果让其再走 x 步刚好能够走完 k 遍环。然而我们并不知道 x，因此可以再搞个slow2节点从head开始，和slow一起走，二者相遇的地方就是我们要求的环的第一个节点。