Write a program to find the node at which the intersection of two singly linked lists begins.
- 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.
For example:
- the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
- begin to intersect at node c1.
C Solution:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if (!headA || !headB) return 0;
struct ListNode *p = headA, *q = headB;
int lenA = 1, lenB = 1;
while (p->next) {
lenA++;
p = p->next;
}
while (q->next) {
lenB++;
q = q->next;
}
if (p != q) return 0;
if (lenA > lenB) {
int m = lenA - lenB;
while (m--) headA = headA->next;
}
else if (lenA < lenB) {
int m = lenB - lenA;
while (m--) headB = headB->next;
}
while (headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
A much better way:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *p = headA, *q = headB;
while (p != q) {
if (p) p = p->next;
else p = headB;
if (q) q = q->next;
else q = headA;
}
return p;
}
Python Solution 1:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB: return
a, b = headA, headB
while a != b:
if not a: a = headB
else: a = a.next
if not b: b = headA
else: b = b.next
return a
Python Solution 2:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
a, b = headA, headB
while a != b:
if not a: a = headB
else: a = a.next
if not b: b = headA
else: b = b.next
return a
Summary:
- Two pass is necessary.
- The second solution is a small cliff.
- The first: 22ms, 98.06%. The second: 23ms, 95.48%
LeetCode: 160. Intersection of Two Linked Lists
近期评论