Linked List Traversal

1 minute read

The Problem

Leetcode 160. Intersection of Two Linked Lists: Write a program to find the node at which the intersection of two singly linked lists begins.

The Solution

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.

intersection-of-2-linkedlists

We observe that

  1. 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.
  2. 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.
  3. 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

The Analysis

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.

Similar problems:

Leetcode 1290. Convert Binary Number in a Linked List to Integer

Updated:

Leave a comment