双指针技巧秒杀七道链表题目

labuladong约 15643 字大约 52 分钟数据结构链表双指针核心框架

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
141. Linked List Cycleopen in new window	141. 环形链表open in new window	🟢
142. Linked List Cycle IIopen in new window	142. 环形链表 IIopen in new window	🟠
160. Intersection of Two Linked Listsopen in new window	160. 相交链表open in new window	🟢
19. Remove Nth Node From End of Listopen in new window	19. 删除链表的倒数第 N 个结点open in new window	🟠
21. Merge Two Sorted Listsopen in new window	21. 合并两个有序链表open in new window	🟢
23. Merge k Sorted Listsopen in new window	23. 合并K个升序链表open in new window	🔴
86. Partition Listopen in new window	86. 分隔链表open in new window	🟠
876. Middle of the Linked Listopen in new window	876. 链表的中间结点open in new window	🟢
-	剑指 Offer 22. 链表中倒数第k个节点open in new window	🟢
-	剑指 Offer 25. 合并两个排序的链表open in new window	🟢
-	剑指 Offer 52. 两个链表的第一个公共节点open in new window	🟢
-	剑指 Offer II 021. 删除链表的倒数第 n 个结点open in new window	🟠
-	剑指 Offer II 022. 链表中环的入口节点open in new window	🟠
-	剑指 Offer II 023. 两个链表的第一个重合节点open in new window	🟢
-	剑指 Offer II 078. 合并排序链表open in new window	🔴

Tip

本文有视频版：链表双指针技巧全面汇总open in new window。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

上次在视频号直播，跟大家说到单链表有很多巧妙的操作，本文就总结一下单链表的基本技巧，每个技巧都对应着至少一道算法题：

1、合并两个有序链表

2、链表的分解

3、合并 k 个有序链表

4、寻找单链表的倒数第 k 个节点

5、寻找单链表的中点

6、判断单链表是否包含环并找出环起点

7、判断两个单链表是否相交并找出交点

这些解法都用到了双指针技巧，所以说对于单链表相关的题目，双指针的运用是非常广泛的，下面我们就来一个一个看。

合并两个有序链表

这是最基本的链表技巧，力扣第 21 题「合并两个有序链表open in new window」就是这个问题：

21. 合并两个有序链表 | 力扣 | LeetCode |

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

示例 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 均按 非递减顺序 排列

给你输入两个有序链表，请你把他俩合并成一个新的有序链表，函数签名如下：

ListNode mergeTwoLists(ListNode l1, ListNode l2);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var mergeTwoLists = function(l1, l2) {
    // function body goes here
};

这题比较简单，我们直接看解法：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;
    
    while (p1 != null && p2 != null) {/**<extend down -200><div class="img-content"><img src="/algo/images/链表技巧/1.gif" class="myimage"/></div> */
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }
    
    if (p1 != null) {
        p.next = p1;
    }
    
    if (p2 != null) {
        p.next = p2;
    }
    
    return dummy.next;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 虚拟头结点
    ListNode* dummy = new ListNode(-1), *p = dummy;
    ListNode* p1 = l1, *p2 = l2;
    
    while (p1 != NULL && p2 != NULL) {/**<extend down -200><div class="img-content"><img src="/algo/images/链表技巧/1.gif" class="myimage"/></div> */
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1->val > p2->val) {
            p->next = p2;
            p2 = p2->next;
        } else {
            p->next = p1;
            p1 = p1->next;
        }
        // p 指针不断前进
        p = p->next;
    }
    
    if (p1 != NULL) {
        p->next = p1;
    }
    
    if (p2 != NULL) {
        p->next = p2;
    }
    
    return dummy->next;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # 虚拟头结点
    dummy = ListNode(-1)
    p = dummy
    p1 = l1
    p2 = l2

    while p1 and p2: # <extend down -200><div class="img-content"><img src="/algo/images/链表技巧/1.gif" class="myimage"/></div> #
        # 比较 p1 和 p2 两个指针
        # 将值较小的的节点接到 p 指针
        if p1.val > p2.val:
            p.next = p2
            p2 = p2.next
        else:
            p.next = p1
            p1 = p1.next
        # p 指针不断前进
        p = p.next

    if p1:
        p.next = p1

    if p2:
        p.next = p2

    return dummy.next

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    // 虚拟头结点
    dummy := &ListNode{-1, nil}
    p := dummy
    p1 := l1
    p2 := l2
    
    for p1 != nil && p2 != nil {/**<extend down -200><div class="img-content"><img src="/algo/images/链表技巧/1.gif" class="myimage"/></div> */
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if p1.Val > p2.Val {
            p.Next = p2
            p2 = p2.Next
        } else {
            p.Next = p1
            p1 = p1.Next
        }
        // p 指针不断前进
        p = p.Next
    }
    
    if p1 != nil {
        p.Next = p1
    }
    
    if p2 != nil {
        p.Next = p2
    }
    
    return dummy.Next
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var mergeTwoLists = function(l1, l2) {
    // 虚拟头结点
    var dummy = new ListNode(-1), p = dummy;
    var p1 = l1, p2 = l2;
    
    while (p1 !== null && p2 !== null) {/**<extend down -200><div class="img-content"><img src="/algo/images/链表技巧/1.gif" class="myimage"/></div> */
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }
    
    if (p1 !== null) {
        p.next = p1;
    }
    
    if (p2 !== null) {
        p.next = p2;
    }
    
    return dummy.next;
};

我们的 while 循环每次比较 p1 和 p2 的大小，把较小的节点接到结果链表上，看如下 GIF：

形象地理解，这个算法的逻辑类似于拉拉链，l1, l2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并；或者说这个过程像蛋白酶合成蛋白质，l1, l2 就好比两条氨基酸，而指针 p 就好像蛋白酶，将氨基酸组合成蛋白质。

代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。你可以试试，如果不使用 dummy 虚拟节点，代码会复杂一些，需要额外处理指针 p 为空的情况。而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。

Tip

经常有读者问我，什么时候需要用虚拟头结点？我这里总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。

单链表的分解

直接看下力扣第 86 题「分隔链表open in new window」：

86. 分隔链表 | 力扣 | LeetCode |

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。

整体逻辑和合并有序链表非常相似，细节直接看代码吧，注意虚拟头结点的运用：

ListNode partition(ListNode head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode p1 = dummy1, p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;

    return dummy1.next;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* partition(ListNode* head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode *dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode *dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode *p1 = dummy1, *p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode *p = head;
    while (p != NULL) {
        if (p->val >= x) {
            p2->next = p;
            p2 = p2->next;
        } else {
            p1->next = p;
            p1 = p1->next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        ListNode *temp = p->next;
        p->next = NULL;
        p = temp;
    }
    // 连接两个链表
    p1->next = dummy2->next;

    return dummy1->next;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
def partition(head: ListNode, x: int) -> ListNode:
    # 存放小于 x 的链表的虚拟头结点
    dummy1 = ListNode(-1)
    # 存放大于等于 x 的链表的虚拟头结点
    dummy2 = ListNode(-1)
    # p1, p2 指针负责生成结果链表
    p1, p2 = dummy1, dummy2
    # p 负责遍历原链表，类似合并两个有序链表的逻辑
    # 这里是将一个链表分解成两个链表
    p = head
    while p:
        if p.val >= x:
            p2.next = p
            p2 = p2.next
        else:
            p1.next = p
            p1 = p1.next
        # 不能直接让 p 指针前进，
        # p = p.next
        # 断开原链表中的每个节点的 next 指针
        temp = p.next
        p.next = None
        p = temp

    # 连接两个链表
    p1.next = dummy2.next

    return dummy1.next

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type ListNode struct {
    Val  int
    Next *ListNode
}

func partition(head *ListNode, x int) *ListNode {
    // 存放小于 x 的链表的虚拟头结点
    dummy1 := &ListNode{-1, nil}
    // 存放大于等于 x 的链表的虚拟头结点
    dummy2 := &ListNode{-1, nil}
    // p1, p2 指针负责生成结果链表
    p1, p2 := dummy1, dummy2
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    p := head
    for p != nil {
        if p.Val >= x {
            p2.Next = p
            p2 = p2.Next
        } else {
            p1.Next = p
            p1 = p1.Next
        }
        // 不能直接让 p 指针前进，
        // p = p.Next
        // 断开原链表中的每个节点的 Next 指针
        temp := p.Next
        p.Next = nil
        p = temp
    }
    // 连接两个链表
    p1.Next = dummy2.Next

    return dummy1.Next
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var partition = function(head, x) {
    // 存放小于 x 的链表的虚拟头结点
    var dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    var dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    var p1 = dummy1, p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    var p = head;
    while (p !== null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        var temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;
    
    return dummy1.next;
}

我知道有很多读者会对这段代码有疑问：

// 不能直接让 p 指针前进，
// p = p.next
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;

不多废话，直接借助我们的可视化面板看一下就明白了。首先看下正确的写法：

如果你不断开原链表中的每个节点的 next 指针，那么就会出错，因为结果链表中会包含一个环：

总的来说，如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。那其实我们可以养成一个好习惯，但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了。

合并 k 个有序链表

看下力扣第 23 题「合并K个升序链表open in new window」：

23. 合并K个升序链表 | 力扣 | LeetCode |

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

函数签名如下：

ListNode mergeKLists(ListNode[] lists);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* mergeKLists(vector<ListNode*>& lists);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def mergeKLists(lists: List[ListNode]) -> ListNode:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func mergeKLists(lists []*ListNode) *ListNode

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var mergeKLists = function(lists) {};

合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？

这里我们就要用到优先级队列（二叉堆）这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    // 虚拟头结点
    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    // 优先级队列，最小堆
    priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq(
        [] (ListNode* a, ListNode* b) { return a->val > b->val; });
    // 将 k 个链表的头结点加入最小堆
    for (auto head : lists) {
        if (head != nullptr) {
            pq.push(head);
        }
    }

    while (!pq.empty()) {
        // 获取最小节点，接到结果链表中
        ListNode* node = pq.top();
        pq.pop();
        p->next = node;
        if (node->next != nullptr) {
            pq.push(node->next);
        }
        // p 指针不断前进
        p = p->next;
    }
    return dummy->next;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List
import heapq

ListNode.lt= lambda self, other: self.val < other.val

def mergeKLists(lists: List[ListNode]) -> ListNode:
    if not lists:
        return None
    # 虚拟头结点
    dummy = ListNode(-1)
    p = dummy
    # 优先级队列，最小堆
    pq = []
    for head in lists:
        if head:
            heapq.heappush(pq, (head.val, head))

    while pq:
        # 获取最小节点，接到结果链表中
        node = heapq.heappop(pq)[1]
        p.next = node
        if node.next:
            heapq.heappush(pq, (node.next.val, node.next))
        # p 指针不断前进
        p = p.next
    return dummy.next

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type ListNode struct {
    Val int
    Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    // 虚拟头结点
    dummy := &ListNode{-1, nil}
    p := dummy
    // 优先级队列，最小堆
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    // 将 k 个链表的头结点加入最小堆
    for _, head := range lists {
        if head != nil {
            heap.Push(&pq, head)
        }
    }

    for pq.Len() > 0 {
        // 获取最小节点，接到结果链表中
        node := heap.Pop(&pq).(*ListNode)
        p.Next = node
        if node.Next != nil {
            heap.Push(&pq, node.Next)
        }
        // p 指针不断前进
        p = p.Next
    }
    return dummy.Next
}

type PriorityQueue []*ListNode

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    node := x.(*ListNode)
    *pq = append(*pq, node)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    node := old[n-1]
    *pq = old[0 : n-1]
    return node
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var mergeKLists = function(lists) {
    if (lists.length === 0) return null;
    // 虚拟头结点
    var dummy = new ListNode(-1);
    var p = dummy;
    // 优先级队列，最小堆
    var pq = new PriorityQueue(lists.length, function(a, b) {return a.val - b.val});
    // 将 k 个链表的头结点加入最小堆
    for (var i = 0; i < lists.length; i++) {
        var head = lists[i]
        if (head !== null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        var node = pq.poll();
        p.next = node;
        if (node.next !== null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
};

这个算法是面试常考题，它的时间复杂度是多少呢？

优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。

单链表的倒数第 k 个节点

从前往后寻找单链表的第 k 个节点很简单，一个 for 循环遍历过去就找到了，但是如何寻找从后往前数的第 k 个节点呢？

那你可能说，假设链表有 n 个节点，倒数第 k 个节点就是正数第 n - k + 1 个节点，不也是一个 for 循环的事儿吗？

是的，但是算法题一般只给你一个 ListNode 头结点代表一条单链表，你不能直接得出这条链表的长度 n，而需要先遍历一遍链表算出 n 的值，然后再遍历链表计算第 n - k + 1 个节点。

也就是说，这个解法需要遍历两次链表才能得到出倒数第 k 个节点。

那么，我们能不能只遍历一次链表，就算出倒数第 k 个节点？可以做到的，如果是面试问到这道题，面试官肯定也是希望你给出只需遍历一次链表的解法。

这个解法就比较巧妙了，假设 k = 2，思路如下：

首先，我们先让一个指针 p1 指向链表的头节点 head，然后走 k 步：

现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针了对吧？

趁这个时候，再用一个指针 p2 指向链表头节点 head：

接下来就很显然了，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上：

这样，只遍历了一次链表，就获得了倒数第 k 个节点 p2。

上述逻辑的代码如下：

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 返回链表的倒数第 k 个节点
ListNode* findFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1 -> next;
    }
    ListNode* p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != nullptr) {
        p2 = p2 -> next;
        p1 = p1 -> next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 返回链表的倒数第 k 个节点
def findFromEnd(head: ListNode, k: int) -> ListNode:
    p1 = head
    # p1 先走 k 步
    for i in range(k):
        p1 = p1.next
    p2 = head
    # p1 和 p2 同时走 n - k 步
    while p1 != None:
        p2 = p2.next
        p1 = p1.next
    # p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 返回链表的倒数第 k 个节点
func findFromEnd(head *ListNode, k int) *ListNode {
    p1 := head
    // p1 先走 k 步
    for i := 0; i < k; i++ {
        p1 = p1.Next
    }
    p2 := head
    // p1 和 p2 同时走 n - k 步
    for p1 != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 返回链表的倒数第 k 个节点
var findFromEnd = function(head, k) {
    var p1 = head;
    // p1 先走 k 步
    for (var i = 0; i < k; i++) {
        p1 = p1.next;
    }
    var p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
};

当然，如果用 big O 表示法来计算时间复杂度，无论遍历一次链表和遍历两次链表的时间复杂度都是 O(N)，但上述这个算法更有技巧性。

很多链表相关的算法题都会用到这个技巧，比如说力扣第 19 题「删除链表的倒数第 N 个结点open in new window」：

19. 删除链表的倒数第 N 个结点 | 力扣 | LeetCode |

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

我们直接看解法代码：

// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}
    
private ListNode findFromEnd(ListNode head, int k) {
    // 代码见上文
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* x = findFromEnd(dummy, n + 1);
    x->next = x->next->next;
    return dummy->next;
}
    
ListNode* findFromEnd(ListNode* head, int k) {
    // 代码见上文
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 主函数
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # 虚拟头结点
    dummy = ListNode(-1)
    dummy.next = head
    # 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    x = findFromEnd(dummy, n + 1)
    # 删掉倒数第 n 个节点
    x.next = x.next.next
    return dummy.next

def findFromEnd(head: ListNode, k: int) -> ListNode:
    # 代码见上文

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 主函数
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 虚拟头结点
    dummy := &ListNode{-1, head}
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    x := findFromEnd(dummy, n + 1)
    // 删掉倒数第 n 个节点
    x.next = x.next.next
    return dummy.next
}
    
func findFromEnd(head *ListNode, k int) *ListNode {
    // 代码见上文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var removeNthFromEnd = function (head, n) {
    // 虚拟头结点
    var dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    var x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}

var findFromEnd = function (head, k) {
    // 代码见上文
}

这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用，可以用我们实现的 findFromEnd 来操作。

不过注意我们又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。

但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。

单链表的中点

力扣第 876 题「链表的中间结点open in new window」就是这个题目，问题的关键也在于我们无法直接得到单链表的长度 n，常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。

如果想一次遍历就得到中间节点，也需要耍点小聪明，使用「快慢指针」的技巧：

我们让两个指针 slow 和 fast 分别指向链表头结点 head。

每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

上述思路的代码实现如下：

ListNode middleNode(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* middleNode(ListNode* head) {
    // 快慢指针初始化指向 head
    ListNode* slow = head;
    ListNode* fast = head;
    // 快指针走到末尾时停止
    while (fast != nullptr && fast->next != nullptr) {
        // 慢指针走一步，快指针走两步
        slow = slow->next;
        fast = fast->next->next;
    }
    // 慢指针指向中点
    return slow;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def middleNode(head: ListNode) -> ListNode:
    # 快慢指针初始化指向 head
    slow = head
    fast = head
    # 快指针走到末尾时停止
    while fast and fast.next:
        # 慢指针走一步，快指针走两步
        slow = slow.next
        fast = fast.next.next
    # 慢指针指向中点
    return slow

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func middleNode(head *ListNode) *ListNode {
    // 快慢指针初始化指向 head
    slow, fast := head, head
    // 快指针走到末尾时停止
    for fast != nil && fast.Next != nil {
        // 慢指针走一步，快指针走两步
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 慢指针指向中点
    return slow
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * 快慢指针初始化指向 head
 * 快指针走到末尾时停止
 * 慢指针走一步，快指针走两步
 * 慢指针指向中点
 */
var middleNode = function(head) {
    var slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

需要注意的是，如果链表长度为偶数，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。

另外，这段代码稍加修改就可以直接用到判断链表成环的算法题上。

判断链表是否包含环

判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：

每当慢指针 slow 前进一步，快指针 fast 就前进两步。

如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

只需要把寻找链表中点的代码稍加修改就行了：

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

bool hasCycle(ListNode* head) {
    // 初始化快慢指针，指向头结点
    ListNode* slow = head;
    ListNode* fast = head;
    // 快指针到尾部时停止
    while (fast && fast->next) {
        // 慢指针走一步，快指针走两步
        slow = slow->next;
        fast = fast->next->next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def hasCycle(head: ListNode) -> bool:
    # 快慢指针初始化指向 head
    slow, fast = head, head
    # 快指针走到末尾时停止
    while fast and fast.next:
        # 慢指针走一步，快指针走两步
        slow = slow.next
        fast = fast.next.next
        # 快慢指针相遇，说明含有环
        if slow == fast:
            return True
    # 不包含环
    return False

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func hasCycle(head *ListNode) bool {
    // 快慢指针初始化指向 head
    slow, fast := head, head
    // 快指针走到末尾时停止
    for fast != nil && fast.Next != nil {
        // 慢指针走一步，快指针走两步
        slow = slow.Next
        fast = fast.Next.Next
        // 快慢指针相遇，说明含有环
        if slow == fast {
            return true
        }
    }
    // 不包含环
    return false
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

function hasCycle(head) {
    // 快慢指针初始化指向 head
    var slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

当然，这个问题还有进阶版，也是力扣第 142 题「环形链表 IIopen in new window」：如果链表中含有环，如何计算这个环的起点？

为了避免读者迷惑，举个例子，环的起点是指下面这幅图中的节点 2：

这里先直接看一下寻找环起点的解法代码：

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;/**<extend down -200><div class="img-content"><img src="/algo/images/双指针/3.jpeg" class="myimage"/></div> */
        }
        // 上面的代码类似 hasCycle 函数
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }

        // 重新指向头结点
        slow = head;/**<extend up -100><div class="img-content"><img src="/algo/images/双指针/2.jpeg" class="myimage"/></div> */
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;/**<extend down -200><div class="img-content"><img src="/algo/images/双指针/3.jpeg" class="myimage"/></div> */
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == nullptr || fast->next == nullptr) {
        // fast 遇到空指针说明没有环
        return nullptr;
    }

    // 重新指向头结点
    slow = head;/**<extend up -100><div class="img-content"><img src="/algo/images/双指针/2.jpeg" class="myimage"/></div> */
    // 快慢指针同步前进，相交点就是环起点
    while (slow != fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def detectCycle(head: ListNode) -> ListNode:
    fast, slow = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            break # <extend down -200><div class="img-content"><img src="/algo/images/双指针/3.jpeg" class="myimage"/></div> #
    if not fast or not fast.next:
        return None
    slow = head # <extend up -100><div class="img-content"><img src="/algo/images/双指针/2.jpeg" class="myimage"/></div> #
    while slow != fast:
        fast = fast.next
        slow = slow.next
    return slow

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func detectCycle(head *ListNode) *ListNode {
    var fast, slow *ListNode
    fast, slow = head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break/**<extend down -200><div class="img-content"><img src="/algo/images/双指针/3.jpeg" class="myimage"/></div> */
        }
    }
    
    if fast == nil || fast.Next == nil {
        return nil
    }

    slow = head/**<extend up -100><div class="img-content"><img src="/algo/images/双指针/2.jpeg" class="myimage"/></div> */
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var detectCycle = function(head) {
    var fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;/**<extend down -200><div class="img-content"><img src="/algo/images/双指针/3.jpeg" class="myimage"/></div> */
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    // 重新指向头结点
    slow = head;/**<extend up -100><div class="img-content"><img src="/algo/images/双指针/2.jpeg" class="myimage"/></div> */
    // 快慢指针同步前进，相交点就是环起点
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};

可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

为什么要这样呢？这里简单说一下其中的原理。

我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

两个链表是否相交

这个问题有意思，也是力扣第 160 题「相交链表open in new window」函数签名如下：

ListNode getIntersectionNode(ListNode headA, ListNode headB);

给你输入两个链表的头结点 headA 和 headB，这两个链表可能存在相交。

如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。

比如题目给我们举的例子，如果输入的两个链表如下图：

那么我们的算法应该返回 c1 这个节点。

这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。

按照这个思路，可以写出如下代码：

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 求链表的交点
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode *p1 = headA, *p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == nullptr) p1 = headB;
        else               p1 = p1->next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == nullptr) p2 = headA;
        else               p2 = p2->next;
    }
    return p1; // 返回交点
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # p1 指向 A 链表头结点，p2 指向 B 链表头结点
    p1, p2 = headA, headB
    while p1 != p2:
        # p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if p1 == None:
            p1 = headB
        else:
            p1 = p1.next
        # p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if p2 == None:
            p2 = headA
        else:
            p2 = p2.next
    return p1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    p1, p2 := headA, headB
    for p1 != p2 {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if p1 == nil {
            p1 = headB
        } else {
            p1 = p1.Next
        }
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if p2 == nil {
            p2 = headA
        } else {
            p2 = p2.Next
        }
    }
    return p1
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * p1 points to the head node of A linked list, p2 points to the head node of B linked list.
 * p1 走一步，如果走到 A 链表末尾，转到 B 链表
 * p2 走一步，如果走到 B 链表末尾，转到 A 链表
 */
function getIntersectionNode(headA, headB) {
    var p1 = headA, p2 = headB;
    while (p1 != p2) {
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

这样，这道题就解决了，空间复杂度为 O(1)，时间复杂度为 O(N)。

以上就是单链表的所有技巧，希望对你有启发。

2022/1/24 更新：

评论区有不少优秀读者对最后一题「寻找两条链表的交点」提出了一些其他思路，也补充到这里。

首先有读者提到，如果把两条链表首尾相连，那么「寻找两条链表的交点」的问题转换成了前面讲的「寻找环起点」的问题：

说实话我没有想到这种思路，不得不说这是一个很巧妙的转换！不过需要注意的是，这道题说不让你改变原始链表的结构，所以你把题目输入的链表转化成环形链表求解之后记得还要改回来，否则无法通过。

另外，还有读者提到，既然「寻找两条链表的交点」的核心在于让 p1 和 p2 两个指针能够同时到达相交节点 c1，那么可以通过预先计算两条链表的长度来做到这一点，具体代码如下：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lenA = 0, lenB = 0;
    // 计算两条链表的长度
    for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
        lenA++;
    }
    for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
        lenB++;
    }
    // 让 p1 和 p2 到达尾部的距离相同
    ListNode p1 = headA, p2 = headB;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            p2 = p2.next;
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    int lenA = 0, lenB = 0;
    // 计算两条链表的长度
    for (ListNode *p1 = headA; p1 != nullptr; p1 = p1->next) {
        lenA++;
    }
    for (ListNode *p2 = headB; p2 != nullptr; p2 = p2->next) {
        lenB++;
    }
    // 让 p1 和 p2 到达尾部的距离相同
    ListNode *p1 = headA, *p2 = headB;
    if (lenA > lenB) {
        // p1 先走过 lenA-lenB 步
        for (int i = 0; i < lenA - lenB; i++) {
            p1 = p1->next;
        }
    } else {
        // p2 先走过 lenB-lenA 步
        for (int i = 0; i < lenB - lenA; i++) {
            p2 = p2->next;
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;  
    }
    return p1;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    lenA, lenB = 0, 0
    # 计算两条链表的长度
    p1, p2 = headA, headB
    while p1:
        lenA += 1
        p1 = p1.next
    while p2:
        lenB += 1
        p2 = p2.next
    # 让 p1 和 p2 到达尾部的距离相同
    p1, p2 = headA, headB
    if lenA > lenB:
        for i in range(lenA - lenB):
            p1 = p1.next
    else:
        for i in range(lenB - lenA):
            p2 = p2.next
    # 看两个指针是否会相同，p1 == p2 时有两种情况：
    # 1、要么是两条链表不相交，他俩同时走到尾部空指针
    # 2、要么是两条链表相交，他俩走到两条链表的相交点
    while p1 != p2:
        p1 = p1.next
        p2 = p2.next
    return p1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA, lenB := 0, 0
    // 计算两条链表的长度
    for p1 := headA; p1 != nil; p1 = p1.Next {
        lenA++
    }
    for p2 := headB; p2 != nil; p2 = p2.Next {
        lenB++
    }    
    // 让 p1 和 p2 到达尾部的距离相同
    p1, p2 := headA, headB
    if lenA > lenB {
        for i := 0; i < lenA-lenB; i++ {
            p1 = p1.Next
        }
    } else {
        for i := 0; i < lenB-lenA; i++ {
            p2 = p2.Next
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    for p1 != p2 {
        p1 = p1.Next
        p2 = p2.Next
    }
    
    return p1
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var getIntersectionNode = function(headA, headB) {
    let lenA = 0, lenB = 0;
    // 计算两条链表的长度
    for (let p1 = headA; p1 !== null; p1 = p1.next) {
        lenA++;
    }
    for (let p2 = headB; p2 !== null; p2 = p2.next) {
        lenB++;
    }
    // 让 p1 和 p2 到达尾部的距离相同
    let p1 = headA, p2 = headB;
    if (lenA > lenB) {
        for (let i = 0; i < lenA - lenB; i++) {
            p1 = p1.next;
        }
    } else {
        for (let i = 0; i < lenB - lenA; i++) {
            p2 = p2.next;
        }
    }
    // 看两个指针是否会相同，p1 == p2 时有两种情况：
    // 1、要么是两条链表不相交，他俩同时走到尾部空指针
    // 2、要么是两条链表相交，他俩走到两条链表的相交点
    while (p1 !== p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
};

虽然代码多一些，但是时间复杂度是还是 O(N)，而且会更容易理解一些。

总之，我的解法代码并不一定就是最优或者最正确的，鼓励大家在评论区多多提出自己的疑问和思考，我也很高兴和大家探讨更多的解题思路~

到这里，链表相关的双指针技巧就全部讲完了，这些技巧的更多扩展延伸见更多双指针经典高频题open in new window。

引用本文的文章

Git原理之最近公共祖先【强化练习】双指针更多经典习题丑数系列算法详解二维数组的花式遍历技巧双指针技巧秒杀七道数组题目如何判断回文链表存储系统设计之 LSM 树原理归并排序详解及应用我的刷题心得本站简介用算法打败算法配套 Chrome 刷题插件（必装）

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
109. Convert Sorted List to Binary Search Treeopen in new window	109. 有序链表转换二叉搜索树open in new window
1257. Smallest Common Regionopen in new window🔒	1257. 最小公共区域open in new window🔒
1650. Lowest Common Ancestor of a Binary Tree IIIopen in new window🔒	1650. 二叉树的最近公共祖先 IIIopen in new window🔒
1836. Remove Duplicates From an Unsorted Linked Listopen in new window🔒	1836. 从未排序的链表中移除重复元素open in new window🔒
2. Add Two Numbersopen in new window	2. 两数相加open in new window
234. Palindrome Linked Listopen in new window	234. 回文链表open in new window
264. Ugly Number IIopen in new window	264. 丑数 IIopen in new window
313. Super Ugly Numberopen in new window	313. 超级丑数open in new window
355. Design Twitteropen in new window	355. 设计推特open in new window
360. Sort Transformed Arrayopen in new window🔒	360. 有序转化数组open in new window🔒
373. Find K Pairs with Smallest Sumsopen in new window	373. 查找和最小的 K 对数字open in new window
378. Kth Smallest Element in a Sorted Matrixopen in new window	378. 有序矩阵中第 K 小的元素open in new window
431. Encode N-ary Tree to Binary Treeopen in new window🔒	431. 将 N 叉树编码为二叉树open in new window🔒
88. Merge Sorted Arrayopen in new window	88. 合并两个有序数组open in new window
97. Interleaving Stringopen in new window	97. 交错字符串open in new window
977. Squares of a Sorted Arrayopen in new window	977. 有序数组的平方open in new window
-	剑指 Offer 18. 删除链表的节点open in new window
-	剑指 Offer 25. 合并两个排序的链表open in new window
-	剑指 Offer 49. 丑数open in new window
-	剑指 Offer 52. 两个链表的第一个公共节点open in new window
-	剑指 Offer II 021. 删除链表的倒数第 n 个结点open in new window
-	剑指 Offer II 022. 链表中环的入口节点open in new window
-	剑指 Offer II 023. 两个链表的第一个重合节点open in new window
-	剑指 Offer II 027. 回文链表open in new window
-	剑指 Offer II 061. 和最小的 k 个数对open in new window
-	剑指 Offer II 078. 合并排序链表open in new window

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 合并两个有序链表

# 单链表的分解

# 合并 k 个有序链表

# 单链表的倒数第 k 个节点

# 单链表的中点

# 判断链表是否包含环

# 两个链表是否相交

合并两个有序链表

单链表的分解

合并 k 个有序链表

单链表的倒数第 k 个节点

单链表的中点

判断链表是否包含环

两个链表是否相交