Intersection of Two Linked Lists 380
Question
Write a program to find the node at which the intersection of two singly linked lists begins.
Notice
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Example
The following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Challenge
Your code should preferably run in O(n) time and use only O(1) memory.
Solution
可以将问题转换为寻找有环的Linked Listd的环的起点。
1) 找到第一个Linked List的最后一个node， 将其和第二个Linked List的head相连
2) 若两个Linked List相交，则一定会形成一个环（若无环则证明不相交，返回null）
3) 再以第一个Linked List的head为起点寻找环的起点即可
4) 为保持两个Linked List结构，最后要将第一个Linked List的最后一个节点指向null
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// Write your code here
if(headA == null || headB == null){
return null;
}
ListNode curt = headA;
while(curt.next != null){
curt = curt.next;
}
curt.next = headB;
ListNode intersection = listCycle(headA);
curt.next = null;
return intersection;
}
private ListNode listCycle(ListNode head){
ListNode slow = head;
ListNode fast = head.next;
while(fast != slow){
if(fast == null || fast.next == null){
return null;
}
slow = slow.next;
fast = fast.next.next;
}
slow = head;
fast = fast.next;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}