Thursday, December 11, 2014
Intersection of Two LinkedList LeetCode (Important)
1. Find the length of each list
2. Scan from the same length of the short list in the longer list.
It should be O(n) time and O(1) space.
It is not easy for me :(
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
//Get the length 0f List A
int indexA = 0;
ListNode tempA = headA;
while (tempA != null) {
tempA = tempA.next;
indexA++;
}
//Get the length of List B
int indexB = 0;
ListNode tempB = headB;
while (tempB != null) {
tempB = tempB.next;
indexB++;
}
//Two pointers
ListNode longNode = (indexA > indexB) ? headA : headB;
ListNode shortNode = (longNode == headA) ? headB : headA;
int diff = Math.abs(indexA - indexB);
while (diff > 0) {
longNode = longNode.next;
diff--;
}
while (longNode != null) {
if (longNode.val == shortNode.val) {
return longNode;
}
longNode = longNode.next;
shortNode = shortNode.next;
}
return null;
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment