题解

题面描述

给定两个单链表的头节点 $headA$ 和 $headB$，请找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，则返回 $null$。
题目保证整个链式结构中不存在环。

输入描述：

• 第一行包含两个整数 $n$ 和 $skipA$，其中 $n$ 表示链表 $A$ 的节点个数，$skipA$ 表示在链表 $A$ 中从头节点到相交节点需要跳过的节点个数。
• 第二行包含 $n$ 个整数，表示链表 $A$ 的各节点值。
• 第三行包含两个整数 $m$ 和 $skipB$，其中 $m$ 表示链表 $B$ 的节点个数，$skipB$ 表示在链表 $B$ 中从头节点到相交节点需要跳过的节点个数。
• 第四行包含 $m$ 个整数，表示链表 $B$ 的各节点值。

若两个链表有相交，则有 $listA[skipA] == listB[skipB]$，且从相交节点开始，两个链表共享后续所有节点；否则输出 $0$。

思路

• 构造链表
  根据输入数据，先构造链表 $A$，并用一个数组保存每个节点的地址，方便后续直接定位到第 $skipA$ 个节点。
  对于链表 $B$，先独立构造前 $skipB$ 个节点，当到达第 $skipB$ 个节点时，如果满足交点条件，则将其接到链表 $A$ 的第 $skipA$ 个节点上，这样两个链表从此节点开始共享后续部分。
• 寻找交点
  采用双指针法。令指针 $pA$ 从 $headA$ 开始遍历，$pB$ 从 $headB$ 开始遍历，每次各自前进一步。当其中一个指针走到链表末尾时，切换到另一个链表的头部。这样当两个链表存在交点时，两个指针会在交点相遇；否则最终都为 $null$。
• 输出
  输出交点的值，如果不存在交点则输出 $0$。

代码分析

• 链表构造部分
  构造链表 $A$ 时，将每个节点地址保存在数组中，以便后续直接定位到交点。
  构造链表 $B$ 时，判断当前节点是否为第 $skipB$ 个节点，若是且存在交点，则直接接上链表 $A$ 的对应节点。
• 双指针法
  使用双指针遍历两个链表，直到两个指针相遇。该方法不需要额外空间，时间复杂度为 $O(n+m)$，非常高效。

C++

#include <iostream>
#include <vector>
using namespace std;

// 链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    // 双指针法寻找两个链表的交点
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (!headA || !headB) return nullptr;
        ListNode* pA = headA;
        ListNode* pB = headB;
        // 当两个指针相遇时，即为交点；若没有交点最终都为nullptr
        while (pA != pB) {
            pA = (pA == nullptr ? headB : pA->next);
            pB = (pB == nullptr ? headA : pB->next);
        }
        return pA;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, skipA;
    cin >> n >> skipA;
    vector<int> vecA(n);
    for (int i = 0; i < n; i++){
        cin >> vecA[i];
    }
    
    int m, skipB;
    cin >> m >> skipB;
    vector<int> vecB(m);
    for (int i = 0; i < m; i++){
        cin >> vecB[i];
    }
    
    // 构造链表 A
    ListNode* headA = new ListNode(vecA[0]);
    ListNode* curA = headA;
    vector<ListNode*> nodesA; // 保存每个节点地址
    nodesA.push_back(headA);
    for (int i = 1; i < n; i++){
        curA->next = new ListNode(vecA[i]);
        curA = curA->next;
        nodesA.push_back(curA);
    }
    
    // 构造链表 B
    ListNode* headB = nullptr;
    ListNode* curB = nullptr;
    // 如果需要相交，则前 skipB 个节点独立构造
    if(m > 0){
        headB = new ListNode(vecB[0]);
        curB = headB;
    }
    for (int i = 1; i < m; i++){
        // 如果 i == skipB 且满足交点条件，则接上链表A的第skipA个节点
        if(i == skipB && skipA < n) {
            curB->next = nodesA[skipA];
            break;
        } else {
            curB->next = new ListNode(vecB[i]);
            curB = curB->next;
        }
    }
    
    // 特殊情况：若 skipB == 0 且满足交点条件，则链表B直接接在链表A的第skipA个节点
    if(skipB == 0 && skipA < n) {
        // 释放原来的headB并指向链表A的交点
        // 注意：此处题目要求构造的链表为交叉链表，所以如果skipB==0则整个链表B就是链表A从skipA开始
        delete headB;
        headB = nodesA[skipA];
    }
    
    Solution sol;
    ListNode* intersect = sol.getIntersectionNode(headA, headB);
    if (intersect) {
        cout << intersect->val << "\n";
    } else {
        cout << 0 << "\n";
    }
    
    return 0;
}

Python

# 定义链表节点类
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # 双指针法寻找交点
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pA, pB = headA, headB
        while pA != pB:
            pA = headB if pA is None else pA.next
            pB = headA if pB is None else pB.next
        return pA

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        exit(0)
    index = 0
    n = int(input_data[index]); index += 1
    skipA = int(input_data[index]); index += 1
    vecA = []
    for _ in range(n):
        vecA.append(int(input_data[index]))
        index += 1
    m = int(input_data[index]); index += 1
    skipB = int(input_data[index]); index += 1
    vecB = []
    for _ in range(m):
        vecB.append(int(input_data[index]))
        index += 1

    # 构造链表A
    headA = ListNode(vecA[0])
    curA = headA
    nodesA = [headA]
    for i in range(1, n):
        node = ListNode(vecA[i])
        curA.next = node
        curA = node
        nodesA.append(node)

    # 构造链表B
    headB = ListNode(vecB[0]) if m > 0 else None
    curB = headB
    for i in range(1, m):
        if i == skipB and skipA < n:
            # 接上链表A的第skipA个节点
            curB.next = nodesA[skipA]
            break
        else:
            node = ListNode(vecB[i])
            curB.next = node
            curB = node

    if skipB == 0 and skipA < n:
        # 如果skipB为0，则链表B直接指向链表A的第skipA个节点
        headB = nodesA[skipA]

    sol = Solution()
    intersect = sol.getIntersectionNode(headA, headB)
    if intersect:
        print(intersect.val)
    else:
        print(0)

Java

import java.util.*;
import java.io.*;

// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Main {
    // 双指针法寻找交点
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while(pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split("\\s+");
        int n = Integer.parseInt(parts[0]);
        int skipA = Integer.parseInt(parts[1]);
        
        String[] arrA = br.readLine().split("\\s+");
        int[] vecA = new int[n];
        for(int i = 0; i < n; i++){
            vecA[i] = Integer.parseInt(arrA[i]);
        }
        
        parts = br.readLine().split("\\s+");
        int m = Integer.parseInt(parts[0]);
        int skipB = Integer.parseInt(parts[1]);
        
        String[] arrB = br.readLine().split("\\s+");
        int[] vecB = new int[m];
        for(int i = 0; i < m; i++){
            vecB[i] = Integer.parseInt(arrB[i]);
        }
        
        // 构造链表A
        ListNode headA = new ListNode(vecA[0]);
        ListNode curA = headA;
        List<ListNode> nodesA = new ArrayList<>();
        nodesA.add(headA);
        for(int i = 1; i < n; i++){
            curA.next = new ListNode(vecA[i]);
            curA = curA.next;
            nodesA.add(curA);
        }
        
        // 构造链表B
        ListNode headB = null;
        if(m > 0) {
            headB = new ListNode(vecB[0]);
        }
        ListNode curB = headB;
        for(int i = 1; i < m; i++){
            if(i == skipB && skipA < n) {
                // 接上链表A的第skipA个节点
                curB.next = nodesA.get(skipA);
                break;
            } else {
                curB.next = new ListNode(vecB[i]);
                curB = curB.next;
            }
        }
        
        if(skipB == 0 && skipA < n) {
            // 如果skipB为0，则链表B直接接到链表A的第skipA个节点上
            headB = nodesA.get(skipA);
        }
        
        ListNode intersect = getIntersectionNode(headA, headB);
        if(intersect != null)
            System.out.println(intersect.val);
        else
            System.out.println(0);
    }
}

Leetcode 22.相交链表-原题链接

题目内容

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

图示两个链表在节点 $c1$ 开始相交：

题目数据 保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

• $intersectVal$- 相交的起始节点的值。如果不存在相交节点，这一值为 $0$
• $listA$ - 第一个链表
• $listB$ - 第二个链表
• $skipA$- 在 $listA$ 中（从头节点开始）跳到交叉节点的节点数
• $skipB$ - 在 $listB$中（从头节点开始）跳到交叉节点的节点数

输入描述

输入一共四行，

• 第一行有两个整数$n,skipA$
• 第二行为$n$个整数，表示$listA$
• 第一行有两个整数$m,skipB$
• 第二行为$m$个整数，表示$listB$

输出描述

一个整数$intersectVal$，表示相交的起始节点的值

样例1

输入

5 2
4 1 8 4 5
6 3
5 6 1 8 4 5

输出

8

说明

相交节点的值为 $8$ （注意，如果两个链表相交则不能为 $0$）。

从各自的表头开始算起，链表 $A$为 $[4,1,8,4,5]$，链表 $B$ 为$[5,6,1,8,4,5]$。

在 $A$ 中，相交节点前有 $2$ 个节点；在 $B$ 中，相交节点前有 $3$ 个节点。

— 请注意相交节点的值不为 $1$，因为在链表$A$ 和链表 $B$ 之中值为 $1$的节点 ($A$ 中第二个节点和 $B$ 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 $A$ 和链表 $B$中值为 $8$ 的节点 ($A$ 中第三个节点，$B$ 中第四个节点) 在内存中指向相同的位置。

样例2

输入

5 3
1 9 1 2 4
3 1
3 2 4

输出

2

说明

相交节点的值为 $2$ （注意，如果两个链表相交则不能为 $0$）。

从各自的表头开始算起，链表 $A$ 为$[1,9,1,2,4]$，链表$B$ 为$[3,2,4]$。

在 $A$中，相交节点前有$3$个节点；在$B$ 中，相交节点前有 $1$ 个节点。

样例3

输入

3 3
2 6 4
2 2
1 5

输出

0

说明

从各自的表头开始算起，链表 $A$ 为 $[2,6,4]$，链表 $B$ 为$[1,5]$。

由于这两个链表不相交，所以$intersectVal$ 必须为 $0$，而 $skipA$ 和 $skipB$ 可以是任意值。

这两个链表不相交，因此输出 $0$

提示

• $listA$ 中节点数目为$m$
• $listB$ 中节点数目为 $n$
• $1 <= m, n <= 3 * 10^4$
• $1 <= Node.val <= 10^5$
• $0 <= skipA <= m$
• $0 <= skipB <= n$
• 如果 $listA$ 和 $listB$ 没有交点，$intersectVal$ 为 $0$
• 如果 $listA$ 和 $listB$有交点，$intersectVal == listA[skipA] == listB[skipB]$