题目信息
时间： 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;
}