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:

image tooltip here

Build the result list and return its head.

Example 1:

image tooltip here

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:

image tooltip here

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;
    }
}

1669 - Merge In Between Linked Lists

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions