Leetcode 160. Intersection of Two Linked Lists: Write a program to find the node at which the intersection of two singly linked lists begins.
We see that there are 3 cases: 1) the 2 linked lists do not intersect, 2) the shorter one is a part of longer one and 3) The 2 linked list intersect at some middle node.
We observe that
- if we start from head node of either link lists, we can reach middle node if there is intersection. Suppose both link lists have the same length, we can just perform typical traversal from both head nodes to the end and compare one by one.
- However, the lengths are generally assumed to be in different length, and for the longer linked list, if we can traverse the from the node whose the remaining length is equivalent to the shorter, linked list, then the problem reduced to statement 1 above. Hence we need to find this node, ie. node C.
- Since both linked lists have different length, the difference of the 2 lists are where this node C can be found.
class ListNode: def __init__(self, x): self.val = x self.next = None def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: headA_length = 0 headB_length = 0 temp = headA while temp is not None: headA_length += 1 temp = temp.next temp = headB while temp is not None: headB_length += 1 temp = temp.next long_node = headA if headA_length > headB_length else headB short_node = headA if long_node is headB else headB for i in range(abs(headA_length - headB_length)): long_node = long_node.next while short_node is not None and long_node is not None: if short_node is long_node: return short_node long_node = long_node.next short_node = short_node.next return None
There are a few loops in the solution, but the constant is deterministic and hence the algorithm is linear or O(n). This example shows that many linked list can be solved with simple traversal of linked lists.