链表相交，找交点
面试题 02.07. 链表相交
力扣题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
示例 2：
示例 3：
思路
简单来说，就是求两个链表交点节点的指针。这里同学们要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
面试题02.07.链表相交_1
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
面试题02.07.链表相交_2
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
否则循环退出返回空指针。
C++代码如下：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while (curA != NULL) { // 求链表A的长度
lenA++;
curA = curA->next;
}
while (curB != NULL) { // 求链表B的长度
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
- 时间复杂度：O(n + m)
- 空间复杂度：O(1)
其他语言版本
Java
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) { // 求链表A的长度
lenA++;
curA = curA.next;
}
while (curB != null) { // 求链表B的长度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
//1. swap (lenA, lenB);
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
//2. swap (curA, curB);
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
Python
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
"""
根据快慢法则，走的快的一定会追上走得慢的。
在这道题里，有的链表短，他走完了就去走另一条链表，我们可以理解为走的快的指针。
那么，只要其中一个链表走完了，就去走另一条链表的路。如果有交点，他们最终一定会在同一个
位置相遇
"""
cur_a, cur_b = headA, headB # 用两个指针代替a和b
while cur_a != cur_b:
cur_a = cur_a.next if cur_a else headB # 如果a走完了，那么就切换到b走
cur_b = cur_b.next if cur_b else headA # 同理，b走完了就切换到a
return cur_a
Go
func getIntersectionNode(headA, headB *ListNode) *ListNode {
curA := headA
curB := headB
lenA, lenB := 0, 0
// 求A，B的长度
for curA != nil {
curA = curA.Next
lenA++
}
for curB != nil {
curB = curB.Next
lenB++
}
var step int
var fast, slow *ListNode
// 请求长度差，并且让更长的链表先走相差的长度
if lenA > lenB {
step = lenA - lenB
fast, slow = headA, headB
} else {
step = lenB - lenA
fast, slow = headB, headA
}
for i:=0; i < step; i++ {
fast = fast.Next
}
// 遍历两个链表遇到相同则跳出遍历
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
javaScript
var getListLen = function(head) {
let len = 0, cur = head;
while(cur) {
len++;
cur = cur.next;
}
return len;
}
var getIntersectionNode = function(headA, headB) {
let curA = headA,curB = headB,
lenA = getListLen(headA),
lenB = getListLen(headB);
if(lenA < lenB) {
[curA, curB] = [curB, curA];
[lenA, lenB] = [lenB, lenA];
}
let i = lenA - lenB;
while(i-- > 0) {
curA = curA.next
}
while(curA && curA !== curB) {
curA = curA.next;
curB = curB.next;
}
return curA;
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录