Problem

Given two linked lists, merge one list into another at alternate positions, if second link list has extra nodes, print them as well

Examples

Example 1:

1
2
3
4

Input: list1 = [1, 2, 3], list2 = [4, 5, 6, 7, 8]
Output: [1, 4, 2, 5, 3, 6]
Remaining nodes from list2: [7, 8]
Explanation: Merged list is formed by taking one element from each list alternately. The remaining elements of list2 are printed.

Example 2:

1
2
3
4

Input: list1 = [1, 3, 5], list2 = [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]
Remaining nodes from list2: []
Explanation: Both lists are merged completely without any remaining nodes.

Solution

Method 1 - Iteration

Approach

  1. Initialize Pointers:

    • Use two pointers to traverse the two lists.
    • Use a pointer to keep track of the current position in the merged list.

  2. Merge Lists:

    • While both lists have remaining nodes, alternate nodes from each list.
    • Append any remaining nodes from the second list after the first list is exhausted.
    • If the first list is exhausted, print the remaining nodes from the second list.

  3. Print Remaining Nodes:

    • If there are any remaining nodes in the second list, print them.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

public class Solution {
    // Function to merge two linked lists at alternate positions
    public void mergeLists(ListNode list1, ListNode list2) {
        ListNode curr1 = list1;
        ListNode curr2 = list2;

        ListNode next1, next2;

        // Traverse both lists and merge
        while (curr1 != null && curr2 != null) {
            next1 = curr1.next;
            next2 = curr2.next;

            curr1.next = curr2;
            curr2.next = next1;
            

            curr1 = next1;
            curr2 = next2;
        }

        // Print remaining nodes of list2, if any
        if (curr2 != null) {
            System.out.println("Remaining nodes from list2:");
            while (curr2 != null) {
                System.out.print(curr2.val + " ");
                curr2 = curr2.next;
            }
            System.out.println();
        }
    }

    // Helper function to print the linked list
    public void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("None");
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] arr1 = {1, 2, 3};
        int[] arr2 = {4, 5, 6, 7, 8};
        ListNode list1 = solution.createLinkedList(arr1);
        ListNode list2 = solution.createLinkedList(arr2);

        System.out.println("Original list1:");
        solution.printLinkedList(list1);

        System.out.println("Original list2:");
        solution.printLinkedList(list2);

        solution.mergeLists(list1, list2);

        System.out.println("Merged list:");
        solution.printLinkedList(list1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution:
    def mergeLists(self, list1: ListNode, list2: ListNode) -> None:
        curr1 = list1
        curr2 = list2

        # Traverse both lists and merge
        while curr1 and curr2:
            next1 = curr1.next
            next2 = curr2.next

            curr1.next = curr2
            curr2.next = next1

            curr1 = next1
            curr2 = next2

        # Print remaining nodes of list2, if any
        if curr2:
            print("Remaining nodes from list2:")
            while curr2:
                print(curr2.val, end=" ")
                curr2 = curr2.next
            print()


# Helper function to print the linked list
def print_linked_list(head):
    current = head
    while current:
        print(f"{current.val} -> ", end="")
        current = current.next
    print("None")


# Example usage
arr1 = [1, 2, 3]
arr2 = [4, 5, 6, 7, 8]
list1 = create_linked_list(arr1)
list2 = create_linked_list(arr2)
solution = Solution()

print("Original list1:")
print_linked_list(list1)

print("Original list2:")
print_linked_list(list2)

solution.mergeLists(list1, list2)

print("Merged list:")
print_linked_list(list1)

Complexity

  • ⏰ Time complexity: O(m + n)
    • Merging Lists: The merging process traverses both lists once, so it has a time complexity of O(m + n), where m is the length of list1 and n is the length of list2.
    • Printing Remaining Nodes: If there are any remaining nodes in list2, printing them would take O(n - m) time.
  • 🧺 Space complexity: O(m + n)
    • Auxiliary Space: O(1), since we are only using a constant amount of extra space for pointers.