This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

describe

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: ,1,2,1000000,1000001,1000002,5 [0] 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.Copy the code

Example 2:

Input: list1 =,1,2,3,4,5,6 [0], a = 2, b = 5, list2 = [1000000100001100002100003100004] the Output: ,1,1000000,1000001,1000002,1000003,1000004,6 [0] Explanation: The blue edges and nodes in the above figure indicate the result.Copy the code

Note:

3 <= list1.length <= 10^4
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10^4
Copy the code

parsing

According to the question, is given two length n and m, respectively list list1 and list2, at the same time two Numbers a and b, are given in the topic request we remove list1 from ath node to BTH node, and list2 access to remove the node position. The idea is simple:

  • Initialize L1_H to list1 to connect list2 to the head node. Initialize L1_tail to list1 to connect the tail node to list1 after list2.
  • Connect list2 to list1’s head node, L1_H, using a while loop to keep looking back
  • Use the while loop to keep looking back for the remaining L1_tail node of list1
  • After connecting list2 to L1_H
  • Use the while loop to find the last node of list2
  • Attach L1_tail to the tail node of list2
  • Return list1 which is the latest concatenated list

answer

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeInBetween(self, list1, a, b, list2):
        """
        :type list1: ListNode
        :type a: int
        :type b: int
        :type list2: ListNode
        :rtype: ListNode
        """
        L1_H = list1
        L1_tail = list1
        while a-1>0:
            L1_H = L1_H.next
            a -= 1
        while b-1>=0:
            L1_tail = L1_tail.next
            b -= 1
        L1_H.next = list2
        while list2:
            if list2.next:
                list2 = list2.next
            else:
                break
        list2.next = L1_tail.next
        return list1
        	      
		
Copy the code

The results

Linked Lists In the Linked submissions. Memory Usage: 10000 ms Submissions In Python online submissions for Merge In Between Linked ListsCopy the code

parsing

And you can simplify the process a little bit, the same idea. In fact, this problem must be right if the code is written out according to the normal logical thinking, but the expert may have a more compact and reasonable organization of the code. I am a little unsure of the solution of other big god to the forum, and found that in fact, it is basically the same traversal and splicing operation of two linked lists. I think maybe I’m sorry about the difficulty of Medium.

answer

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeInBetween(self, list1, a, b, list2):
        """
        :type list1: ListNode
        :type a: int
        :type b: int
        :type list2: ListNode
        :rtype: ListNode
        """
        head = list1
        for _ in range(a-1):
            head = head.next
        cur = head.next
        for _ in range(b-a):
            cur = cur.next
        head.next = list2
        while head.next:
            head = head.next
        if cur.next:
            head.next = cur.next
        return list1
Copy the code

The results

Linked Lists In the Linked submissions. Memory Usage: 10000 ms. Submissions In Python online submissions for Merge In Between Linked Lists.Copy the code

Original link: leetcode.com/problems/me…

Your support is my biggest motivation