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

• Java
• C++
• Python

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

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

• # 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
  
  

All Problems

All Solutions