DSCPPAS273 - Editorial

editorial
, ,
1

Problem Statement:

Given two singly linked lists, find the node where the two lists intersect. If there is no intersection, return -1. The lengths of the two linked lists are N and M.

Approach:

Key Observations:

  1. Intersection Point: If two linked lists intersect, then the nodes after the intersection point will be the same for both lists.
  2. Lengths Mismatch: If the lengths of the two linked lists are different, aligning the ends of the lists helps in identifying the intersection point.

Using Two-Pointer Technique:

  • Step 1: Calculate the lengths of both linked lists.
  • Step 2: Align the starting point of both lists so that the remaining lengths of both lists are the same.
    • If one list is longer, advance its pointer by the difference in lengths.
  • Step 3: Traverse both lists together until the pointers meet at the intersection point.

Time Complexity:

  • The solution runs in O(N + M) time, where N and M are the lengths of the two linked lists. This is because each list is traversed at most twice.

Space Complexity:

  • The space complexity is O(1) as no extra space is used other than a few variables.

Example:

Let’s consider two linked lists:

List 1: 1 -> 2 -> 3 -> 4 -> 5
List 2: 9 -> 4 -> 5

  • The lists intersect at node with value 4. The intersection point should return 4.