Leetcode 160 相交链表(intersection-of-two-linked-lists) 题解分析

发表于 更新于 分类于 ， ， ， ， 阅读次数： 阅读次数： Disqus：

题目介绍

写一个程序找出两个单向链表的交叉起始点，可能是我英语不好，图里画的其实还有一点是交叉以后所有节点都是相同的
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

1
2
3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

分析题解

一开始没什么头绪，感觉只能最原始的遍历，后来看了一些文章，发现比较简单的方式就是先找两个链表的长度差，因为从相交点开始肯定是长度一致的，这是个很好的解题突破口，找到长度差以后就是先跳过长链表的较长部分，然后开始同步遍历比较 A，B 链表；

代码

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // 算 A 的长度
        int countA = 0;
        ListNode tailA = headA;
        while (tailA != null) {
            tailA = tailA.next;
            countA++;
        }
        // 算 B 的长度
        int countB = 0;
        ListNode tailB = headB;
        while (tailB != null) {
            tailB = tailB.next;
            countB++;
        }
        tailA = headA;
        tailB = headB;
        // 依据长度差，先让长的链表 tail 指针往后移
        if (countA > countB) {
            while (countA > countB) {
                tailA = tailA.next;
                countA--;
            }
        } else if (countA < countB) {
            while (countA < countB) {
                tailB = tailB.next;
                countB--;
            }
        }
        // 然后以相同速度遍历两个链表比较
        while (tailA != null) {
            if (tailA == tailB) {
                return tailA;
            } else {
                tailA = tailA.next;
                tailB = tailB.next;
            }
        }
        return null;
    }

总结

可能缺少这种思维，做的还是比较少，所以没法一下子反应过来，需要锻炼，我的第一反应是两重遍历，不过那样复杂度就高了，这里应该是只有 O(N) 的复杂度。