Problem

Given two sorted linked lists, write an algorithm to print the common elements of these lists. The solution should be based on the logic of merge sort. Since the elements in the lists are sorted, we can use a two-pointer technique to efficiently find and print the common elements.

Examples:

Example 1:

1
2

Input: list1 = [1, 2, 4, 6, 8], list2 = [2, 4, 6, 8, 10]
Output: [2, 4, 6, 8]

Example 2:

1
2

Input: list1 = [1, 3, 5], list2 = [2, 4, 6]
Output: []

Solution

Method 1 - Using Merge sort logic

  1. Initialize Two Pointers:

    • Use two pointers to traverse both lists, starting from the heads of list1 and list2.

  2. Traverse and Compare:

    • Run a loop until you reach the end of either list.
    • Compare the values of the nodes pointed to by the two pointers.
    • If the values are equal, it means the current element is common in both lists. Print it or add it to the common list.
    • If the value in list1 is less than the value in list2, move the pointer in list1 forward.
    • If the value in list1 is greater than the value in list2, move the pointer in list2 forward.
    • If the values are equal, move both pointers forward.

  3. Return the Result:

    • The common elements are printed or returned as required.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
    public ListNode findCommonElements(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1 = list1.next;
            } else if (list1.val > list2.val) {
                list2 = list2.next;
            } else { // list1.val == list2.val
                current.next = new ListNode(list1.val);
                current = current.next;
                list1 = list1.next;
                list2 = list2.next;
            }
        }

        return dummy.next;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def findCommonElements(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode(0)
        current = dummy

        while list1 and list2:
            if list1.val < list2.val:
                list1 = list1.next
            elif list1.val > list2.val:
                list2 = list2.next
            else:  # list1.val == list2.val
                current.next = ListNode(list1.val)
                current = current.next
                list1 = list1.next
                list2 = list2.next

        return dummy.next

Complexity

  • ⏰ Time complexity: O(m + n), where m and n are the lengths of list1 and list2 respectively. We traverse both lists once.
  • 🧺 Space complexity: O(l), where L is the number of common elements.