参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

# 面试题 02.07. 链表相交

力扣题目链接 (opens new window)

给你两个单链表的头节点 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
  • 时间复杂度:$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;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

C:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *l = NULL, *s = NULL;
    int lenA = 0, lenB = 0, gap = 0;
    // 求出两个链表的长度
    s = headA;
    while (s) {
        lenA ++;
        s = s->next;
    }
    s = headB;
    while (s) {
        lenB ++;
        s = s->next;
    }

    // 求出两个链表长度差
    if (lenA > lenB) {
        l = headA, s = headB;
        gap = lenA - lenB;
    } else {
        l = headB, s = headA;
        gap = lenB - lenA;
    }

    // 尾部对齐
    while (gap--) l = l->next;
    // 移动,并检查是否有相同的元素
    while (l) {
        if (l == s) return l;
        l = l->next, s = s->next;
    }

    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

上次更新:: 1/4/2022, 10:38:57 AM
@2021-2022 代码随想录 版权所有 粤ICP备19156078号-3