Intersection in a linked List

Problem Statement

deeksha sharma
Algorithm Problems
3 min readNov 20, 2015

--

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists, begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Approach

If the intersection point exists and both linked lists are of same size then its easy to find node. But when the sizes are different, then we know the number of nodes after the intersection point in both lists are same.Therefore, the number of nodes would only differ before the intersection point. If we move d(difference in length of 2 lists) nodes in the longer list first and then start moving through both lists, then the size of both would be same from this point.

Find the length of both linked lists and check which of the below conditions meet:

  • Size of both linked lists is same.
  • If this is the case, start from the head of both the linked lists. Move one node at time and keep checking if the nodes are same. If yes, then we found the intersecting node else if we reach null then there is no intersecting node.
  • One of the linked list is greater than the other one.
  • In this case, calculate the difference (d) between the lengths of 2 linked lists.
  • Traverse through the longer linked list first and move d nodes. After reaching the dth node, start traversing the short linked list and long linked list in parallel. Check each node from both the linked lists for equality. Return the intersecting node if found else return null.

Run Time

The run time complexity of this code is O(n)

Java Code

--

--

deeksha sharma
Algorithm Problems

Work for https://bonsaiilabs.com/ life long learner ,investing time heavily in personal finance, education, tech and design skills. Twitter: @deekshasharma25