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 1:
Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] Output: [10,1,13,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.
Example 2:
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 <= 1041 <= a <= b < list1.length - 11 <= list2.length <= 104This approach involves using two pointers to identify the nodes in list1 where list2 will be inserted.
First, traverse list1 to reach the node right before the ath node. Next, continue to traverse to just beyond the bth node. The node at this position serves as the connection to the remainder of list1 after the insertion point.
Finally, link the identified nodes with list2.
In this C solution, we define a struct ListNode and operate on pointers within the linked list. First, we traverse to just before the ath position in list1 (prevA), and then traverse from there to just beyond the bth node (nodeB) in list1. After that, we link prevA to list2 and traverse to the end of list2 to link it to nodeB.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m) where n is the number of nodes in list1 up to b and m is the length of list2. Space Complexity: O(1) as we use a constant amount of auxiliary space.
This approach solves the problem recursively, leveraging recursive traversal to reach the split points on list1 and link list2 in the required section of list1.
Base cases are established for when the algorithm should stop the recursive calls and perform actions to connect the segments together.
C does not naturally support recursive list manipulations easily, especially without introducing significant complications. Therefore, this approach is better showcased in languages with better support for recursive structures.
C++
Java
Python
C#
JavaScript
Complexity details are not provided for C in recursive solutions.
| Approach | Complexity |
|---|---|
| Using Two Pointers | Time Complexity: O(n + m) where n is the number of nodes in |
| Recursive Approach | Complexity details are not provided for C in recursive solutions. |
Merge Two Sorted Lists - Leetcode 21 - Python • NeetCode • 438,617 views views
Watch 9 more video solutions →Practice Merge In Between Linked Lists with our built-in code editor and test cases.
Practice on FleetCode