Intersection of Two Linked Lists
描述
Write a program to find the node at which the intersection of two singly linked lists begins.
Example 1:
Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
Output: The node with value = 8
Notes:
- 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.
- Your code should preferably run in O(n) time and use only O(1) memory.
分析
最自然的想法，是先遍历完两个单链表，得到他们的长度lenA和lenB，进而知道他们的长度之差。然后再次遍历两个单链表，不过这次，长的单链表先走|lenA-lenB|步，然后两个指针一起走，当两个指针指向相同的节点，这个节点就是相交点。这个算法的时间复杂度是 O(m+n)，空间复杂度 O(1)，是符合题目要求的。
上述思路遍历了两边，可以优化为只遍历一遍。遍历两个单链表，较短的那条会最先到达尾部，然后把这个指针指向较长的单链表的头部（这等价于让长链表的指针先走|lenA-lenB|步），两个指针继续往前走，当两个指针指向相同的节点时，这个指针就是相交点。
代码
- Java
- C++
// Intersection of Two Linked Lists
// Two Pointers
// Time Complexity: O(m+n), Space Complexity: O(1)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while( a != b) {
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
}
// Intersection of Two Linked Lists
// Two Pointers
// Time Complexity: O(m+n), Space Complexity: O(1)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) return nullptr;
ListNode * a = headA;
ListNode * b = headB;
while ( a != b) {
a = a == nullptr? headB : a->next;
b = b == nullptr? headA : b->next;
}
return a;
}
};