Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1669.html
Question
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 incidate the result:
Build the result list and return its head.
Example 1:
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.
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.
Algorithm
给定两个链表l1和l2,要求将l1的下标为a ∼ b的节点删除,并且将l2插在中间。返回新链表头。题目保证a和b下标都合法。 先找到l1下标为a − 1的节点,然后找到下标为b + 1的节点,接着将l2接到a − 1节点后面,再找到l2的尾节点,连到b + 1节点前面。代码如下:
Code
-
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode start2 = list2, end2 = list2; while (end2.next != null) end2 = end2.next; ListNode insertStart = list1, insertEnd = list1; for (int i = 1; i < a; i++) insertStart = insertStart.next; for (int i = 0; i <= b; i++) insertEnd = insertEnd.next; insertStart.next = start2; end2.next = insertEnd; return list1; } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode p = list1, q = list1; while (--a > 0) { p = p.next; } while (b-- > 0) { q = q.next; } p.next = list2; while (p.next != null) { p = p.next; } p.next = q.next; q.next = null; return list1; } }
-
// OJ: https://leetcode.com/problems/merge-in-between-linked-lists/ // Time: O(N) // Space: O(1) class Solution { public: ListNode* mergeInBetween(ListNode* A, int a, int b, ListNode* B) { ListNode *q = A, *p = NULL; for (int i = 0; i < b; ++i) { if (i == a - 1) p = q; q = q->next; } p->next = B; while (B->next) B = B->next; B->next = q->next; return A; } };
-
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeInBetween( self, list1: ListNode, a: int, b: int, list2: ListNode ) -> ListNode: p = q = list1 for _ in range(a - 1): p = p.next for _ in range(b): q = q.next p.next = list2 while p.next: p = p.next p.next = q.next q.next = None return list1 ############ # 1669. Merge In Between Linked Lists # https://leetcode.com/problems/merge-in-between-linked-lists/ # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode: res = head = curr = ListNode() curr.next = list1 l = -1 while curr: if l == a: head = curr.next if l == b: c = list2 while c.next: c = c.next curr = curr.next while curr: c.next = curr curr = curr.next c = c.next break curr = curr.next l += 1 l = -1 temp = res while temp and l+1 != a: temp = temp.next l += 1 temp.next = list2 return res.next
-
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode { p, q := list1, list1 for ; a > 1; a-- { p = p.Next } for ; b > 0; b-- { q = q.Next } p.Next = list2 for p.Next != nil { p = p.Next } p.Next = q.Next q.Next = nil return list1 }
-
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function mergeInBetween( list1: ListNode | null, a: number, b: number, list2: ListNode | null, ): ListNode | null { let p = list1; let q = list1; while (--a > 0) { p = p.next; } while (b-- > 0) { q = q.next; } p.next = list2; while (p.next) { p = p.next; } p.next = q.next; q.next = null; return list1; }
-
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode p = list1, q = list1; while (--a > 0) { p = p.next; } while (b-- > 0) { q = q.next; } p.next = list2; while (p.next != null) { p = p.next; } p.next = q.next; q.next = null; return list1; } }