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.
Solution:
If two linked lists have a intersection, it should look like this:
The length of A is x + z, and the length of B is y + z.
Let's traverse step by step from A and B.
We find if B travels y + z to the end of the list, and travels x more steps from the beginning of linked list A, it travels y + z + x steps.
If A travels x + z to the end of the list, and travels y more steps from the beginning of linked list B, it also travels y + z + x steps.
And both of them will arrive the intersection.
Code:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode p1 = headA; ListNode p2 = headB; while (p1 != p2) { p1 = p1 == null ? headB : p1.next; p2 = p2 == null ? headA : p2.next; } return p1; } }