Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
求两个链表的交点，要求Time: O(n), Space: O(1)
解法1：交点最早可能出现在短链表的第一个节点，后面的节点两个链表一样。所以，长链表的比短链表开始多出的那些就没用。求出两个链表的长度差值，把较长的链表向后移动这个差值，变成一样长。然后在一个一个的比较。
解法2: 双指针，用两个指针pA和pB分别指向链表A和B。然后让它们分别遍历整个链表，每步一个节点。当pA到达链表末尾时，让它指向B的头节点（没错，是B）；类似的当pB到达链表末尾时，重新指向A的头节点。如果pA在某一点与pB相遇，则pA/pB就是交集开始的节点。
Java： Solution 1
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
int lenA = getLength(headA), lenB = getLength(headB);
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
} else {
for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
}
while (headA != null && headB != null && headA != headB) {
headA = headA.next;
headB = headB.next;
}
return (headA != null && headB != null) ? headA : null;
}
public int getLength(ListNode head) {
int cnt = 0;
while (head != null) {
++cnt;
head = head.next;
}
return cnt;
}
}
Java: Solution 2
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode a = headA, b = headB;
while (a != b) {
a = (a != null) ? a.next : headB;
b = (b != null) ? b.next : headA;
}
return a;
}
}
Python:
class Solution:
# @param two ListNodes
# @return the intersected ListNode
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None
pa = headA # 2 pointers
pb = headB
while pa is not pb:
# if either pointer hits the end, switch head and continue the second traversal,
# if not hit the end, just move on to next
pa = headB if pa is None else pa.next
pb = headA if pb is None else pb.next
return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None
# the idea is if you switch head, the possible difference between length would be countered.
# On the second traversal, they either hit or miss.
# if they meet, pa or pb would be the node we are looking for,
# if they didn't meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None
Python: wo
class Solution(object):
def getIntersectionNode(self, headA, headB):
if not headA or not headB:
return None
a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
Python: Solution 1
class Solution(object):
def getIntersectionNode(self, headA, headB):
lenA = self.getListLen(headA)
lenB = self.getListLen(headB)
if lenA > lenB:
for i in range(lenA - lenB):
headA = headA.next
elif lenA < lenB:
for i in range(lenB - lenA):
headB = headB.next
while headA != headB:
headA, headB = headA.next, headB.next
return headA
def getListLen(self, head):
length = 0
while head:
length += 1
head = head.next
return length
Python: Solution 2
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# @param two ListNodes
# @return the intersected ListNode
def getIntersectionNode(self, headA, headB):
curA, curB = headA, headB
begin, tailA, tailB = None, None, None
# a->c->b->c
# b->c->a->c
while curA and curB:
if curA == curB:
begin = curA
break
if curA.next:
curA = curA.next
elif tailA is None:
tailA = curA
curA = headB
else:
break
if curB.next:
curB = curB.next
elif tailB is None:
tailB = curB
curB = headA
else:
break
return begin
C++：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
int lenA = getLength(headA), lenB = getLength(headB);
if (lenA < lenB) {
for (int i = 0; i < lenB - lenA; ++i) headB = headB->next;
} else {
for (int i = 0; i < lenA - lenB; ++i) headA = headA->next;
}
while (headA && headB && headA != headB) {
headA = headA->next;
headB = headB->next;
}
return (headA && headB) ? headA : NULL;
}
int getLength(ListNode* head) {
int cnt = 0;
while (head) {
++cnt;
head = head->next;
}
return cnt;
}
};
C++:
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
ListNode *a = headA, *b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};
类似题目：
[LeetCode] 349. Intersection of Two Arrays 两个数组相交
[LeetCode] 350. Intersection of Two Arrays II 两个数组相交II