Sponsored
Sponsored
First, traverse both linked lists to determine their lengths. Calculate the difference in lengths and advance the pointer of the longer list by the length difference. Then move both pointers in tandem to find the intersection node.
Time Complexity: O(m + n).
Space Complexity: O(1).
1public class Solution {
2 public class ListNode {
3 int val;
4 ListNode next;
5 ListNode(int x) {
6 val = x;
7 next = null;
8 }
9 }
10
11 private int getLength(ListNode head) {
12 int length = 0;
13 while (head != null) {
14 length++;
15 head = head.next;
16 }
17 return length;
18 }
19
20 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
21 int lenA = getLength(headA);
22 int lenB = getLength(headB);
23
24 if (lenA > lenB) {
25 for (int i = 0; i < lenA - lenB; i++) headA = headA.next;
26 } else {
27 for (int i = 0; i < lenB - lenA; i++) headB = headB.next;
28 }
29
30 while (headA != headB) {
31 headA = headA.next;
32 headB = headB.next;
33 }
34 return headA;
35 }
36}The solution in Java determines the length of each list and adjusts the pointers if one list is longer than the other before checking each node for intersection.
Use two pointers, each starting at the head of one list. Traverse the list until a pointer reaches null, then start traversing the other list from the beginning. Repeat until the two pointers meet at the intersection node.
Time Complexity: O(m + n).
Space Complexity: O(1).
1class
The Python solution follows the two pointer method where each pointer traverses its list, and when reaching the end, starts from the beginning of the other list. This continues until they meet at an intersection node or at the end as null.