[LeetCode] Merge In Between Linked Lists

Problem: You are given two linked lists: list1 and list2 of sizes n and m respectively. Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

The blue edges and nodes in the following figure indicate the result:

Build the result list and return its head.

Example:

Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [0,1,2,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints:

• 3 <= list1.length <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

Approach: The approach is straight forward. We will store the (a - 1)th node and (b + 1)th node of list1. Now we can put list2 to the next of (a - 1)th node of list1. We traverse the whole list2 and in the end we will put the stored (b + 1)th node of list1 to the next of end of list2 and that's all.

Implementation in C#: 

    public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) 

    {

        ListNode node = list1;

        ListNode mergeStartNode = null;

        for (int i = 0; i <= b; ++i)

        {

            if (i == a - 1)

            {

                mergeStartNode = node;

            }        

            node = node.next;

        }        

        ListNode mergeEndNode = node;

        mergeStartNode.next = list2;

        node = list2;

        while (node.next != null)

        {

            node = node.next;

        }

        node.next = mergeEndNode;

        return list1;

    }

Complexity: O(n)