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).
1class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6class Solution:
7 def getLength(self, head):
8 length = 0
9 while head:
10 length += 1
11 head = head.next
12 return length
13
14 def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
15 lenA = self.getLength(headA)
16 lenB = self.getLength(headB)
17
18 if lenA > lenB:
19 for _ in range(lenA - lenB):
20 headA = headA.next
21 else:
22 for _ in range(lenB - lenA):
23 headB = headB.next
24
25 while headA != headB:
26 headA = headA.next
27 headB = headB.next
28 return headAThe Python solution calculates the length of each list. If one is longer, it advances that pointer by the difference. Both pointers are then compared step by step until the intersection is found.
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).
1public class Solution {
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; next = null; }
}
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}The C# solution uses two pointers, initialized at the heads of the lists. They switch to the other list's head at the end of the current list traversal and continue until they meet at the intersection node or return null.