Simple ,Beginner friendly & Dry Run & Advanced Sol, Full Explanation||Time O(n) Space O(1)||Gits✅✅✅
\n\n# Intuition \uD83D\uDC48\n\nIn the question, we are given two linked lists, List1 and List2, and two numbers, a and b. We have to remove nodes of List1 from
![Screenshot 2024-02-08 135653.png](https://assets.leetcode.com/users/images/538bbf3f-1826-4675-8ac1-dda7d9b392f5_1707380820.4163773.png)\n\n# Intuition \uD83D\uDC48\n\nIn the question, we are given two linked lists, List1 and List2, and two numbers, a and b. We have to remove nodes of List1 from a to b and insert List2 in their place.\n\n# Approach \uD83D\uDC48\n\nTo solve this question, we will simply create a dummy list with a random value and a `prev` node, which will point to the node previous to `a`. Then, we will create a node `after_idx`, which will point to the node next to `b`. Next, we will set `prev.next` to point to `list2`. We will create a node `last_idx`, which will point to the last node of `list2`. Finally, we will set `last_idx.next` to point to `after_idx`.\n\n![Screenshot 2024-02-08 140738.png](https://assets.leetcode.com/users/images/29475909-2206-449f-aa4f-fac3fc325f35_1707381470.4974391.png)\n\n# Code Explanation \uD83D\uDC48\n\n\n*   **Creating a Dummy Node**: A new `ListNode` named `dummy` is created with a value of `0`. This node does not actually hold data relevant to the lists being merged but serves as a placeholder to simplify manipulation of the list heads and ensure uniform handling of all nodes during the merge. `dummy.next` is set to point to the head of `list1`, effectively placing the dummy node at the beginning of `list1`.\n    \n*   **Locating the Insertion Point**: The method starts by finding the node in `list1` immediately before the position `a` where `list2` will be inserted. This is done by advancing a pointer `pre` from the dummy node up to, but not including, the `a`th node. This loop runs `a` times.\n    \n*   **Skipping Over Nodes to be Replaced**: Another pointer, `last`, is set to the position of `pre` and then advanced to the node immediately after position `b`, effectively locating the part of `list1` that will remain after the nodes from `a` to `b` are replaced by `list2`. This loop runs `(b - a + 1)` times to include both the start and end positions in the count.\n    \n*   **Inserting `list2` into `list1`**: The `next` pointer of the node just before `a` (now held by `pre`) is set to point to the head of `list2`, beginning the process of insertion by linking the end of the preserved start segment of `list1` to the beginning of `list2`.\n    \n*   **Finding the End of `list2`**: The code then iterates through `list2` to find its last node, using a pointer `tail2`. This is necessary to connect the end of `list2` back into `list1`.\n    \n*   **Completing the Merge**: Once the end of `list2` is found, `tail2.next` is set to `last`, which points to the node immediately after position `b` in `list1`. This links the end of `list2` to the remainder of `list1`, completing the merge.\n    \n*   **Returning the Merged List**: Finally, the method returns `dummy.next`. Since `dummy` was initially set to point to the head of `list1`, and `list1` was modified to include `list2`, `dummy.next` now points to the head of the fully merged list. The use of the dummy node means the head of the merged list is returned correctly, even if `list2` was inserted at the very start of `list1`.\n\n# Complexity \uD83D\uDC48\n- Time complexity: O(n) Where n is the sum of length of the Linked Lists .\n\n- Space complexity: O(1)\n\n# Code \uD83D\uDC48\n\n```C []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     struct ListNode *next;\n * };\n */\n\n\nstruct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2){\n    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); // Corrected type casting\n    dummy->val = 0;\n    dummy->next = list1;\n    struct ListNode* prev = dummy;\n\n    for(int i = 0; i < a; i++) {\n        prev = prev->next;\n    }\n\n    struct ListNode* after_idx = prev;\n    for(int i = a; i <= b + 1; i++) {\n        after_idx = after_idx->next;\n    }\n\n    struct ListNode* last_idx = list2;\n    while(last_idx->next != NULL) {\n        last_idx = last_idx->next;\n    }\n\n    last_idx->next = after_idx;\n    prev->next = list2;\n\n    struct ListNode* result = dummy->next;\n    free(dummy); \n    return result;\n}\n```\n```C++ []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {\n        ListNode* dummy = new ListNode(0);\n        dummy->next = list1;\n        ListNode* prev = dummy;\n        for(int i=0; i<a; i++){\n            prev = prev->next;\n        }\n        ListNode* after_idx  = prev;\n        for(int i = a; i<= b+1; i++){\n            after_idx = after_idx->next;\n        }\n        ListNode* last_idx = list2;\n        while(last_idx->next != NULL){\n            last_idx = last_idx->next;\n        }\n        last_idx->next = after_idx;\n        prev->next = list2;\n        return dummy->next;\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 dummy = new ListNode(0);\n        dummy.next = list1;\n        ListNode prev = dummy;\n        for(int i=0; i<a; i++){\n            prev = prev.next;\n        }\n        ListNode after_idx  = prev;\n        for(int i = a; i<= b+1; i++){\n            after_idx = after_idx.next;\n        }\n        ListNode last_idx = list2;\n        while(last_idx.next != null){\n            last_idx = last_idx.next;\n        }\n        last_idx.next = after_idx;\n        prev.next = list2;\n        return dummy.next;\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        dummy = new ListNode(0);\n        dummy.next = list1;\n        prev = dummy;\n        for(let i=0; i<a; i++){\n            prev = prev.next;\n        }\n        after_idx  = prev;\n        for(let i = a; i<= b+1; i++){\n            after_idx = after_idx.next;\n        }\n        last_idx = list2;\n        while(last_idx.next != null){\n            last_idx = last_idx.next;\n        }\n        last_idx.next = after_idx;\n        prev.next = list2;\n        return dummy.next;\n};\n```\n```C# []\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     public int val;\n *     public ListNode next;\n *     public ListNode(int val=0, ListNode next=null) {\n *         this.val = val;\n *         this.next = next;\n *     }\n * }\n */\npublic class Solution {\n    public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) {\n        ListNode dummy = new ListNode(0);\n        dummy.next = list1;\n        ListNode prev = dummy;\n        for(int i=0; i<a; i++){\n            prev = prev.next;\n        }\n        ListNode after_idx  = prev;\n        for(int i = a; i<= b+1; i++){\n            after_idx = after_idx.next;\n        }\n        ListNode last_idx = list2;\n        while(last_idx.next != null){\n            last_idx = last_idx.next;\n        }\n        last_idx.next = after_idx;\n        prev.next = list2;\n        return dummy.next;\n    }\n}\n```\n```python []\n# Definition for singly-linked list.\n# class ListNode(object):\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution(object):\n    def mergeInBetween(self, list1, a, b, list2):\n        """\n        :type list1: ListNode\n        :type a: int\n        :type b: int\n        :type list2: ListNode\n        :rtype: ListNode\n        """\n        dummy = ListNode(0)\n        dummy.next = list1\n        pre = dummy\n\n        for _ in range(0,a):\n            pre = pre.next\n\n        last = pre\n\n        for _ in range(a, b+2):\n            last = last.next\n\n        pre.next = list2\n        tail2 = list2\n\n        while tail2.next != None:\n            tail2 = tail2.next\n    \n        tail2.next = last\n        return dummy.next\n```\n```ruby []\n# Definition for singly-linked list.\n# class ListNode\n#     attr_accessor :val, :next\n#     def initialize(val = 0, _next = nil)\n#         @val = val\n#         @next = _next\n#     end\n# end\n# @param {ListNode} list1\n# @param {Integer} a\n# @param {Integer} b\n# @param {ListNode} list2\n# @return {ListNode}\ndef merge_in_between(list1, a, b, list2)\n    dummy = ListNode.new(0)\n        dummy.next = list1\n        pre = dummy\n\n        for i in 0..a-1 do\n            pre = pre.next\n        end\n\n        last = pre\n\n        for i in a..b+1 do\n            last = last.next\n        end\n\n        pre.next = list2\n        tail2 = list2\n\n        while tail2.next != nil \n            tail2 = tail2.next\n        end\n        tail2.next = last\n        return dummy.next\nend\n```\n\n\n# Dry Run  \uD83D\uDC48\n\n1.  **Traverse to Node Before `a`**: The loop runs until `i < a`, moving `pre` to point to the node just before the `a`th node in `list1`. For `a = 3`, `pre` ends up pointing to the node with value `2`.\n    \n2.  **Find Node After `b`**: Another loop runs to move the `last` pointer to the node just after `b`, which for `b = 4`, ends up pointing to the node with value `5`.\n    \n3.  **Insert `list2` into `list1`**: The `next` of `pre` (which points to `2`) is set to the head of `list2` (`1000000`). This operation effectively begins the process of inserting `list2` between the nodes `2` and `5` of `list1`.\n    \n4.  **Find Last Node of `list2`**: Iteration through `list2` finds the last node, which has the value `1000002`.\n    \n5.  **Link the Last Node of `list2` to `list1`**: The `next` of the last node of `list2` (`1000002`) is set to `last`, which points to the node with value `5` in `list1`.\n    \n6.  **Result**: The `dummy.next` is returned, which now points to the head of the modified `list1`.\n    \n\nHere\'s how the lists change at each step:\n\n*   **Original list1**: `0 -> 1 -> 2 -> 3 -> 4 -> 5`\n*   **list2**: `1000000 -> 1000001 -> 1000002`\n\n**After Step 2**: `pre` points to `2`.\n\n**After Step 3**: `last` points to `5`.\n\n**After Step 4**: `list1` changes to `0 -> 1 -> 2 -> 1000000 -> 1000001 -> 1000002` (temporarily disconnected from the rest of `list1`).\n\n**After Step 6**: The connection is completed as `1000002 -> 5`.\n\n**Final merged list**: `0 -> 1 -> 2 -> 1000000 -> 1000001 -> 1000002 -> 5`\n\nThus, nodes `3` and `4` from `list1` have been replaced by all nodes from `list2`, and the final list after the operation is `[0, 1, 2, 1000000, 1000001, 1000002, 5]`.\n\n# Guys if the explanation and solution is helpful then up vote me.\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![Screenshot 2024-02-08 140339.png](https://assets.leetcode.com/users/images/c041042e-f8a2-4655-ac6a-ac75d641fcfa_1707381239.987448.png)\n
['Linked List', 'C', 'Python', 'C++', 'Java', 'Python3', 'Ruby', 'JavaScript', 'C#']