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

Java

public class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode dummy = new ListNode(0), prev = dummy;
        dummy.next = list1;

        for (int i = 0; i < a; i++) {
            prev = prev.next;
        }

        ListNode next = prev;
        for (int i = 0; i < b - a + 2; i++) {
            next = next.next;
        }

        prev.next = list2;
        while (prev.next != null) {
            prev = prev.next;
        }

        prev.next = next;
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

Java

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

All Problems

All Solutions