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 <= 104
1 <= a <= b < list1.length - 1
1 <= list2.length <= 104
Solutions
Solution 1: Simulation
We can directly simulate the operations described in the problem.
In the implementation, we use two pointers $p$ and $q$, both initially pointing to the head node of list1.
Then we move pointers $p$ and $q$ forward, until pointer $p$ points to the node before the $a$-th node in list1, and pointer $q$ points to the $b$-th node in list1. At this point, we set the next pointer of $p$ to the head node of list2, and set the next pointer of the tail node of list2 to the node pointed to by the next pointer of $q$. This completes the operation required by the problem.
The time complexity is $O(m + n)$, and the space complexity is $O(1)$. Where $m$ and $n$ are the lengths of list1 and list2 respectively.
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defmergeInBetween(self,list1:ListNode,a:int,b:int,list2:ListNode)->ListNode:p=q=list1for_inrange(a-1):p=p.nextfor_inrange(b):q=q.nextp.next=list2whilep.next:p=p.nextp.next=q.nextq.next=Nonereturnlist1
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcmergeInBetween(list1*ListNode,aint,bint,list2*ListNode)*ListNode{p,q:=list1,list1for;a>1;a--{p=p.Next}for;b>0;b--{q=q.Next}p.Next=list2forp.Next!=nil{p=p.Next}p.Next=q.Nextq.Next=nilreturnlist1}