Basic Approach | | Easy Explanation | | Time O(n) , Space O(1) | | C++ | | Java | | Python3 | | ✅✅🔥
\n\nIntuition:\n\nTo solve this problem, we need to traverse list1 to find the nodes at positions a and b. Once we locate these nodes, we can splice list2 betwe
\n![image.png](https://assets.leetcode.com/users/images/1b4454b1-4b46-4e69-a9b4-423ab7da8c39_1710894607.463631.png)\n**Intuition:**\n\nTo solve this problem, we need to traverse `list1` to find the nodes at positions `a` and `b`. Once we locate these nodes, we can splice `list2` between them. We\'ll connect the node before position `a` to the head of `list2`, and the last node of `list2` to the node after position `b`. \n\n**Approach:**\n\n1. Traverse `list1` to find the node at position `a-1`, `a`, and `b+1`.\n2. Attach the last node of `list2` to the node after position `b`.\n3. Attach the node before position `a` to the head of `list2`.\n4. Return the head of `list1`.\n\n**Complexity:**\n- Time complexity: O(n), where n is the size of `list1` since we traverse it once to find the positions.\n- Space complexity: O(1), as we use a constant amount of extra space.\n\n**Code with Story:**\n\n```C++ []\nclass Solution {\npublic:\n    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {\n        ListNode *prev = list1;  // Initialize pointers to traverse list1\n        ListNode *temp1 = list1;  // Modified variable name\n        ListNode *curr = list1;\n        a--;  // Adjust a to match zero-based indexing\n        \n        // Traverse list1 to find the node at position (a-1)\n        while(temp1 != NULL && a--) {\n            temp1 = temp1->next;\n            prev = temp1;\n        }\n        \n        temp1 = list1;  // Reset temp1 to traverse list1 again\n        \n        // Traverse list1 to find the node at position (b+1)\n        while(temp1 != NULL && b--) {\n            temp1 = temp1->next;\n            curr = temp1;\n        }\n        \n        ListNode *temp2 = list2;  // Initialize pointer to traverse list2\n        \n        // Traverse list2 to find the last node\n        while(temp2->next != NULL) {\n            temp2 = temp2->next;\n        }\n        \n        prev->next = list2;  // Connect the node before position \'a\' to the head of list2\n        temp2->next = curr->next;  // Connect the last node of list2 to the node after position \'b\'\n        \n        return list1;  // Return the head of list1\n    }\n};\n\n```\n```Java []\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {\n        ListNode prev = list1, temp1 = list1, curr = list1;\n        a--; // Adjust a to match zero-based indexing\n        \n        // Traverse list1 to find the node at position (a-1)\n        while (temp1 != null && a-- > 0) {\n            temp1 = temp1.next;\n            prev = temp1;\n        }\n        \n        temp1 = list1; // Reset temp1 to traverse list1 again\n        \n        // Traverse list1 to find the node at position (b+1)\n        while (temp1 != null && b-- > 0) {\n            temp1 = temp1.next;\n            curr = temp1;\n        }\n        \n        ListNode temp2 = list2; // Initialize pointer to traverse list2\n        \n        // Traverse list2 to find the last node\n        while (temp2.next != null) {\n            temp2 = temp2.next;\n        }\n        \n        prev.next = list2; // Connect the node before position \'a\' to the head of list2\n        temp2.next = curr.next; // Connect the last node of list2 to the node after position \'b\'\n        \n        return list1; // Return the head of list1\n    }\n}\n\n```\n```Python3 []\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n        prev = list1\n        temp1 = list1\n        curr = list1\n        a -= 1  # Adjust a to match zero-based indexing\n        \n        # Traverse list1 to find the node at position (a-1)\n        while temp1 and a > 0:\n            temp1 = temp1.next\n            prev = temp1\n            a -= 1\n        \n        temp1 = list1  # Reset temp1 to traverse list1 again\n        \n        # Traverse list1 to find the node at position (b+1)\n        while temp1 and b > 0:\n            temp1 = temp1.next\n            curr = temp1\n            b -= 1\n        \n        temp2 = list2  # Initialize pointer to traverse list2\n        \n        # Traverse list2 to find the last node\n        while temp2.next:\n            temp2 = temp2.next\n        \n        prev.next = list2  # Connect the node before position \'a\' to the head of list2\n        temp2.next = curr.next  # Connect the last node of list2 to the node after position \'b\'\n        \n        return list1  # Return the head of list1\n```\n\n```Kotlin []\n/**\n * Example:\n * var li = ListNode(5)\n * var v = li.`val`\n * Definition for singly-linked list.\n * class ListNode(var `val`: Int) {\n *     var next: ListNode? = null\n * }\n */\nclass Solution {\n    fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?): ListNode? {\n        var prev = list1\n        var temp1 = list1\n        var curr = list1\n        var aCopy = a - 1 // Adjust a to match zero-based indexing\n        \n        // Traverse list1 to find the node at position (a-1)\n        while (temp1 != null && aCopy > 0) {\n            temp1 = temp1.next\n            prev = temp1\n            aCopy--\n        }\n        \n        temp1 = list1 // Reset temp1 to traverse list1 again\n        \n        // Traverse list1 to find the node at position (b+1)\n        var bCopy = b\n        while (temp1 != null && bCopy > 0) {\n            temp1 = temp1.next\n            curr = temp1\n            bCopy--\n        }\n        \n        var temp2 = list2 // Initialize pointer to traverse list2\n        \n        // Traverse list2 to find the last node\n        while (temp2?.next != null) {\n            temp2 = temp2.next\n        }\n        \n        prev?.next = list2 // Connect the node before position \'a\' to the head of list2\n        temp2?.next = curr?.next // Connect the last node of list2 to the node after position \'b\'\n        \n        return list1 // Return the head of list1\n    }\n}\n```\n```JavaScript []\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.next = (next===undefined ? null : next)\n * }\n */\n/**\n * @param {ListNode} list1\n * @param {number} a\n * @param {number} b\n * @param {ListNode} list2\n * @return {ListNode}\n */\nvar mergeInBetween = function(list1, a, b, list2) {\n    let prev = list1, temp1 = list1, curr = list1;\n    a--; // Adjust a to match zero-based indexing\n    \n    // Traverse list1 to find the node at position (a-1)\n    while (temp1 && a-- > 0) {\n        temp1 = temp1.next;\n        prev = temp1;\n    }\n    \n    temp1 = list1; // Reset temp1 to traverse list1 again\n    \n    // Traverse list1 to find the node at position (b+1)\n    while (temp1 && b-- > 0) {\n        temp1 = temp1.next;\n        curr = temp1;\n    }\n    \n    let temp2 = list2; // Initialize pointer to traverse list2\n    \n    // Traverse list2 to find the last node\n    while (temp2.next !== null) {\n        temp2 = temp2.next;\n    }\n    \n    prev.next = list2; // Connect the node before position \'a\' to the head of list2\n    temp2.next = curr.next; // Connect the last node of list2 to the node after position \'b\'\n    \n    return list1; // Return the head of list1\n};\n```\n\n\n**Dry Run:**\n\n\n**Here\'s a step-by-step execution of the code using the specified input:**\n\n1. **Initialization:**\n   - `prev`: points to head of `list1` (node 0).\n   - `temp1`: points to head of `list1` (node 0).\n   - `curr`: points to head of `list1` (node 0).\n   - `a`: decremented to 1 (for zero-based indexing).\n\n2. **Traverse list1 to position (a-1):**\n   - Loop iterates once:\n     - `temp1` moves to node 1 (value 1).\n     - `prev` also moves to node 1 (value 1).\n   - After loop:\n     - `prev` points to node 1 (value 1).\n     - `temp1` points to node 2 (value 2).\n\n3. **Reset temp1 and traverse list1 to position (b+1):**\n   - `temp1` is reset back to head of `list1` (node 0).\n   - Loop iterates 5 times:\n     - `temp1` moves to node 5 (value 5).\n     - `curr` also moves to node 5 (value 5).\n   - After loop:\n      - `curr` points to node 6 (value 6).\n\n4. **Find last node of list2:**\n   - `temp2` iterates through `list2` until it reaches the last node (node 1000004).\n\n5. **Merge the lists:**\n   - `prev->next` (node 1\'s next pointer) is set to `list2` (connecting node 1 to `list2`).\n   - `temp2->next` (last node of `list2`\'s next pointer) is set to `curr->next` (connecting `list2` to node 6).\n\n**Final Output:**\n- The modified `list1` becomes: [0, 1, 1000000, 1000001, 1000002, 1000003, 1000004, 6].\n- Nodes from index 2 to 5 of the original `list1` are effectively replaced with `list2`.\n\n**Edge Cases:**\n- If `list1` is empty.\n- If `list2` is empty.\n- If `a` is 0 (edge case for the beginning of the list).\n- If `b` is the last index of `list1` (edge case for the end of the list).
['Linked List', 'C++', 'Java', 'Python3', 'Kotlin', 'JavaScript']