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 → b3begin 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.
Analysis:
3 steps:
- Get the length of both list
- Let the longer list to go before len1-len2 steps
- Make the lists go further, if they’re the same, then we find it
Time complexity: O(m + n)
Space complexity: O(1)
Code is below:
/** * 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) { // O(m + n) if (headA == null || headB == null) { return null; } int lenA = getLength(headA); int lenB = getLength(headB); // Let the longer list to go before lenA - lenB for (int i = 0; i < Math.abs(lenA - lenB); i++) { if (lenA > lenB) { headA = headA.next; } else { headB = headB.next; } } while (headA != null && headB != null) { if (headA == headB) { return headA; } headA = headA.next; headB = headB.next; } return null; } public int getLength(ListNode head) { int len = 0; while (head != null) { head = head.next; len++; } return len; } }