每日一题 - 剑指 Offer 52. 两个链表的第一个公共节点

每日一题 - 剑指 Offer 52. 两个链表的第一个公共节点

题目信息

时间： 2019-07-03

题目链接：Leetcode

tag： 单链表

难易程度：简单

题目描述：

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

示例:

A： a1 -> a2 \ -> c1 -> c2 -> c3 / B：b1 -> b2 -> b3

注意

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

解题思路

本题难点

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

具体思路

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

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

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

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

代码

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

代码

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; }