#P4015. 相交链表
-
ID: 2222
Tried: 288
Accepted: 58
Difficulty: 4
-
算法标签>数据结构链表
相交链表
题目内容
给你两个单链表的头节点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∗104
- 1<=Node.val<=105
- 0<=skipA<=m
- 0<=skipB<=n
- 如果 listA 和 listB 没有交点，intersectVal 为 0
- 如果 listA 和 listB有交点，intersectVal==listA[skipA]==listB[skipB]
题解
题面描述
给定两个单链表的头节点 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);
}
}