salmon-isle

duhelan07@outlook.com

归档

MISC

标签：双指针

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

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

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)$ 。

2026-10-29

[算法] LC21 – 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists

含 C 和 JAVA 两种语言的题解

1. 题目描述

题目：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入/输出样例：

// 样例 1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

// 样例 2
输入：l1 = [], l2 = []
输出：[]

// 样例 3
输入：l1 = [], l2 = [0]
输出：[0]

// 样例 1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

// 样例 2
输入：l1 = [], l2 = []
输出：[]

// 样例 3
输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

2. 【方法一】双指针

@Krahets 题解，查看原文

一、思路

两个链表 l1、l2 都是递增的，可以想到用双指针 l1 和 l2 遍历两链表，根据 l1.val 和 l2.val 的大小关系确定添加顺序。

两个节点指针交替前进，直到遍历完毕。

因为初始状态下，合并链表（结果链表）中无节点，循环第一轮时无法将节点添加到合并链表中，所以需要初始化一个伪头节点 dum（Dummy Node 的缩写），将各节点添加到 dum 之后。

伪头节点也叫哨兵节点、哑节点，其 val 值是随便给的，这里用 0 。伪头节点和数据结构中常引入的头节点（Head Node）不一样：

伪头节点是辅助性的、临时性的，用完即弃，不作为结果的一部分；
而数据结构教材中常提到的头节点，本身是链表的一部分

二、算法流程

初始化：伪头节点 dum，节点 cur 指向 dum （在 C 语言里就是让 cur 和 dum 存放相同的内存地址，类似“引用传递”的感觉）。
循环合并：当 l1 或 l2 为空时跳出。
1. 当 l1.val < l2.val 时：cur 的后继节点指定为 l1，并 l1 向前走一步。
2. 当 l1.val >= l2.val 时：cur 的后继节点指定为 l2，并 l2 向前走一步。
3. 节点 cur 向前走一步，即 cur = cur.next。
合并剩余尾部：跳出时有两种情况，即 l1 为空或 l2 为空。
1. 若 l1 != null：将 l1 添加至节点 cur 之后。
2. 否则：将 l2 添加至节点 cur 之后。
返回值：合并链表在伪头节点 dum 之后，因此返回 dum.next 即可。

三、代码 & 复杂度分析

C 代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = dum;

    while(l1 != NULL && l2 != NULL) {
        if (l1->val >= l2->val) {
            cur->next = l2;
            l2 = l2->next;
        }
        else {
            cur->next = l1;
            l1 = l1->next;
        }
        cur = cur->next;
    }

    cur->next = l1 != NULL ? l1 : l2;

    return dum->next;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = dum;

    while(l1 != NULL && l2 != NULL) {
        if (l1->val >= l2->val) {
            cur->next = l2;
            l2 = l2->next;
        }
        else {
            cur->next = l1;
            l1 = l1->next;
        }
        cur = cur->next;
    }

    cur->next = l1 != NULL ? l1 : l2;

    return dum->next;
}

Java 代码（@Krahets）：

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dum = new ListNode(0), cur = dum;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            }
            else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return dum.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dum = new ListNode(0), cur = dum;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            }
            else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return dum.next;
    }
}

复杂度分析：

时间：因为需要遍历 l1、l2 两个链表，假设它们的长度为 M, N，那么时间复杂度就是 O(M + N)；
空间：空间复杂度为 O(1)，仅需要 dum，cur 两个常数大小的额外空间。

3. 【方法二】递归法

@腐烂的橘子 + 官方题解

一、思路

我不看题解完全想不到这个方法，甚至有的题解只要四行就能解决问题（可读性为 0）。不过递归法的时间复杂度仍为 O(M + N)，而空间复杂度也为 O(M + N)，似乎并没有比双指针法更好。

对于本题目：

终止条件：两个链表都为空，表示链表已经合并完成；
如何递归：我们判断 l1 和 l2 的头节点哪个更小，然后让较小结点的 next 指向其余结点的合并结果。

写好一个递归就是考虑清楚三个问题：

这个问题的子问题是什么（原问题是合并 l1 和 l2，子问题就是【合并 l1.next 和 l2 两个链表，或合并 l2->next 和 l1 两个链表】）；
当前层要干什么事情（选出值较小的头节点，作为合并后链表的头结点，把 next 指向剩余两个链表合并后的结果，即递归调用的返回值，然后将这个结果返回给本层比出的较小头节点）；
递归出口（两个链表有一个为空）。

不能习惯地往深处想，不断地想下一层，这样永远想不清楚。

二、代码 & 复杂度分析

C 代码：

// 节点定义略
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 递归出口
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }

    // 当前层
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

// 节点定义略
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 递归出口
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }

    // 当前层
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

Java 代码（@腐烂的橘子）：

Java

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

复杂度分析：

时间：递归函数每次去掉一个元素，直到两个链表都为空，因此需要调用 R = O(m+n) 次。而在递归函数中我们只进行了 next 指针的赋值操作，复杂度为 O(1)，故递归的总时间复杂度为 O(T) = R ∗ O(1) = O(m+n) 。
空间：因为一共调用了 m+n 次，所以使用了 m+n 个栈帧，故空间复杂度为 O(m+n)。

2026-10-25

标签： 双指针

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

LC160 – 相交链表

一、题目描述

二、思路

三、代码 & 复杂度分析

LC206 – 反转链表

一、题目描述

二、思路 & 代码

1. 迭代法

2. 递归法

三、复杂度分析

LC234 – 回文链表

一、题目描述

二、思路 & 代码

三、复杂度分析

[算法] LC21 – 合并两个有序链表

1. 题目描述

2. 【方法一】双指针

一、思路

二、算法流程

三、代码 & 复杂度分析

3. 【方法二】递归法

一、思路

二、代码 & 复杂度分析

标签：双指针