题目信息

  • 题目；剑指 Offer 52. 两个链表的第一个公共节点

  • 时间： 2020-08-21

  • 题目链接：Leetcode

  • tag： 单链表

  • 难易程度：简单

  • 题目描述：

    输入两个链表，找出它们的第一个公共节点。

示例:

1
2
3
4
5
A：      a1 -> a2 
                 \
									-> c1 -> c2 -> c3
                 /
B：b1 -> b2 -> b3

注意

1
2
3
4
1. 如果两个链表没有交点，返回 null.
2. 在返回结果后，两个链表仍须保持原有的结构。
3. 可假定整个链表结构中没有循环。
4. 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路

本题难点

两条链表不一样长，其到达交点的路程不一样。时间复杂度有要求。

具体思路

使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历。

  • 当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；

  • 当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

当它们相遇时，所指向的结点就是第一个公共结点。

注意

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode node1 = headA;
        ListNode node2 = headB;
      //两分叉长度一致时，即A B链表长度相同且存在公共节点，此时，不等node1走完A链表(node2走完B链表)即可获得公共节点;
      //两分叉不同且存在公共节点时，此时即为最开始分析时的思路，node1,node2分别走完两链表的所有长度，并在节点处相遇。
      //不存在公共节点，此时最终离开循环时,node1=node2=null,两链表A，B长度相同时，node1,node2只要分别遍历完自己的那条链表就行; 两链表长度不同时,node1先遍历A链表,再遍历B链表,node2先遍历B链表,再遍历A链表,由于A链表+B链表长度固定，等价于node1,node2分别遍历一条长度为A+B的链表，最终一起指向null，循环结束；
        while(node1 != node2){
            node1 = node1 != null ? node1.next : headB;
            node2 = node2 != null ? node2.next : headA;
        }
        return node1;
    }
}

复杂度分析：

  • 时间复杂度 O(M+N) ：第一个链表的长度为 m,第二个链表的长度为n，两链表遍历一次花费的时间。
  • 空间复杂度 O(1) ： 使用常数大小的额外空间。

其他优秀解答

解题思路

双链指针同时移动，确保同时到链表尾。先确定哪个指针路程长，让其先走几个结点。

  • 辅助函数getLength(ListNode head)用于计数某个链表的长度：通过移动指针temp的循环确定链表长度。
  • 通过lengthA与lengthB大小，判断哪个指针先走，先走的指针要走的步数即为abs(lengthA-lengthB)。
  • “站在同一起跑线后”，就可以指针每移动一次，判断是否走到同一个结点，若是，该结点即为交结点。

对于没有交点的情况，最终a与b会同时成为null，然后while循环结束，返回a也就是null

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA = getLength(headA), lengthB = getLength(headB);
        ListNode a = headA, b = headB;
        if(lengthA > lengthB){
            for(int i = 0; i < lengthA - lengthB; i++)
                a = a.next;
        } else {
            for(int i = 0; i < lengthB - lengthA; i++)
                b = b.next;
        }
        while(a != b){
            a = a.next;
            b = b.next;
        }
        return a;
    }
    private int getLength(ListNode head){
        int length = 0;
        for(ListNode temp = head; temp != null; temp = temp.next, length++);
        return length;
    }