# Linked List Traversal

## 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.

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
```

## 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

## Leave a comment