三道链表简单题（但是也有不好想的地方）

LC160 – 相交链表

一、题目描述

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

输入 / 输出样例：

Plaintext

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection

二、思路

（没有题解来源，因为高赞题解基本没区别）

我原本的想法是写一个 getlen(*L) 函数，先获取 A、B 两个链表的长度，计算其长度之差，然后根据长度差挪动指针，使两个指针对齐。

没想到题解仅用五行就解决了问题：

假设 A、B 链表的长度分别为 $a + c$ 和 $b + c$ （其中 c 是公共部分）。

如果我们尝试组合两个链表，有两种方式，AB 和 BA（即 B 接在 A 后，和 A 接在 B 后），其长度分别为 $a + c + b + c$ 和 $b + c + a + c$ ；
我们注意到： $a + c + b = b + c + a$ ；
也就是说，如果我们用两个指针，从 A 和 B 的头部开始，分别遍历链表 AB 和链表 BA，在一定能同时到达末尾的同时（因为 AB 和 BA 长度相等），也一定能同时进入最后的公共段 c（因为进入最后的公共段之前，两个指针走过的长度相等）。

所以：

我们只需要创建两个指针 aPtr 和 bPtr，分别从 A、B 的头节点开始遍历；
当 aPtr 遍历到 A 末尾时，跳转到 B 的头部开始遍历；
当 bPtr 遍历到 B 末尾时，跳转到 A 的头部开始遍历；
两个指针一定能找到相交之点（或最后都为 null）。

三、代码 & 复杂度分析

Java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode aPtr = headA, bPtr = headB;
        
        while (aPtr != bPtr) {
            aPtr = (aPtr == null) ? headB : aPtr.next;
            bPtr = (bPtr == null) ? headA : bPtr.next;
        }

        return aPtr;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode aPtr = headA, bPtr = headB;
        
        while (aPtr != bPtr) {
            aPtr = (aPtr == null) ? headB : aPtr.next;
            bPtr = (bPtr == null) ? headA : bPtr.next;
        }

        return aPtr;
    }
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *A = headA, *B = headB;
    while (A != B) {
        A = A != NULL ? A->next : headB;
        B = B != NULL ? B->next : headA;
    }
    return A;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *A = headA, *B = headB;
    while (A != B) {
        A = A != NULL ? A->next : headB;
        B = B != NULL ? B->next : headA;
    }
    return A;
}

复杂度分析：

时间：最坏的情况下两个链表都要完全遍历，那么时间就是 $O(M + N)$ ；
空间：空间复杂度为 $O(1)$ ，只需常数级的额外变量。

LC206 – 反转链表

一、题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

二、思路 & 代码

最简单的问题，无需多言

1. 迭代法

使用三个指针 prev、curr 和 next。

每次循环时，先暂存当前结点的下一个结点，令当前结点指向 prev，然后更新 prev 和 curr（都向后挪一位）。

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

2. 递归法

考虑清楚一个递归问题就是想明白退出条件、子问题和当前层这三件事：

退出条件（也就是不再继续深入、开始回溯的条件）：指针 p 到达原本的末尾结点，此时的 p 就是新 head；
子问题：这个问题的子问题就是“把 p 之后的那部分链表反转好”。在子问题完成之后，p->next 这个链表就已经是反向的了（反转之后 p->next 是尾节点）；
当前层要做的事：在当前层，只需要调好 p 和 p->next 的连接就行了，即让 p->next 指向自己，然后让自己指向 null。

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 反转后，整条链表的新头，值始终不变
        ListNode newHead = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 反转后，整条链表的新头，值始终不变
        ListNode newHead = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }
}

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

三、复杂度分析

迭代法的时间复杂度为 O(n)，空间复杂度为 O(1)；
递归法的时间、空间复杂度均为 O(n)（因为栈区将有 n 个函数入栈）。

LC234 – 回文链表

一、题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

true

二、思路 & 代码

用快慢指针找到链表的中点，反转链表的后半部分，然后迭代比较链表的前半和反转后的后半。

快慢指针：当快指针 fast 到达末尾时，慢指针 slow 恰好会到达中点处。

这题也可以使用递归，但我不想再研究递归了，感觉不是很有必要

Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode sHead = reverseList(slow.next);
        ListNode p1 = head, p2 = sHead;
        boolean result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        
        // 将后半部分恢复
        slow.next = reverseList(sHead);
        return result;
    }
    
    // 反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode sHead = reverseList(slow.next);
        ListNode p1 = head, p2 = sHead;
        boolean result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        
        // 将后半部分恢复
        slow.next = reverseList(sHead);
        return result;
    }
    
    // 反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;

    while (curr != NULL) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return true;

    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct ListNode* sHead = reverseList(slow->next);
    struct ListNode* p1 = head;
    struct ListNode* p2 = sHead;
    bool result = true;
    
    while (p2 != NULL) {
        if (p1->val != p2->val) {
            result = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    slow->next = reverseList(sHead);
    return result;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;

    while (curr != NULL) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return true;

    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct ListNode* sHead = reverseList(slow->next);
    struct ListNode* p1 = head;
    struct ListNode* p2 = sHead;
    bool result = true;
    
    while (p2 != NULL) {
        if (p1->val != p2->val) {
            result = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    slow->next = reverseList(sHead);
    return result;
}

三、复杂度分析

时间：

找中点：遍历 N/2 个节点，耗时 $O(N)$ ；
反转后半部分链表：遍历 N/2 个节点，耗时 $O(N)$ ；
比较两个链表：最坏情况同样是遍历 N/2 个节点，耗时 $O(N)$ ；
恢复原链表： $O(N)$ ；
总的时间复杂度是 $O(2N) = O(N)$ 。

空间：只使用常数级的额外空间，复杂度为 $O(1)$ 。

标签： 快慢指针

[算法] LC160, 206, 234 – 相交, 反转和回文链表

LC160 – 相交链表

一、题目描述

二、思路

三、代码 & 复杂度分析

LC206 – 反转链表

一、题目描述

二、思路 & 代码

1. 迭代法

2. 递归法

三、复杂度分析

LC234 – 回文链表

一、题目描述

二、思路 & 代码

三、复杂度分析

标签：快慢指针