Merge two ordered linked lists

LeetCode21. Merge two ordered linked lists

Problem description

Input two monotonically increasing linked lists and output the synthesized linked list. We need the synthesized linked list to meet the monotonic non decreasing rule.

Example:

Input: {1,3,5}, {2,four,6}

Return value: {1,2,3,4,5,6}

Analyze problems

Since the given two linked lists are ordered, we can judge the value of the head node of the two linked lists, add the node with the smaller value to the result, and then move the node pointer of the corresponding linked list back one bit and cycle until one of the linked lists is empty.

Because the linked list is ordered, when the loop terminates, the elements in the non empty linked list are larger than those in the merged linked list. Therefore, we just need to simply connect the non empty linked list to the merged linked list and return to the merged linked list.

First, we need to create a sentinel node, and then point the prehead to the smaller one in the linked list l1 and l2. If equal, point to any one. Then move the pointer of the linked list corresponding to the smaller value back one bit.

Let's take a look at the code implementation.

def mergeTwoLists(self, l1, l2):
        #Sentinel node of the merged linked list
        head=ListNode(-1,None)
        pre=head
        #Loop traversal, inserting the smaller value in the two linked lists into the merged linked list
        while l1 and l2:
            if l1.val <= l2.val:
                pre.next=l1
                l1=l1.next
            else:
                pre.next=l2
                l2=l2.next
            pre=pre.next
        #Insert the remaining non empty linked list after the merged linked list
        if l1:
            pre.next=l1
        else:
            pre.next=l2

        return head.next

In fact, we can also use recursion here.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, l1, l2):
        #The linked list l1 is empty and does not need to be merged. l2 is returned directly
        if(l1==None):
            return l2
        #Similarly, if l2 is empty, you can directly return l1    
        if(l2==None):
            return l1

        if(l1.val<=l2.val):
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2

Problem escalation

LeetCode23. Merge K ascending linked lists

Next, let's upgrade the problem and change the merging of two ordered linked lists into the merging of multiple ordered linked lists. Let's take a look at the problem.

Given an ordered linked list, each node also represents an ordered linked list. A node contains two types of pointers:

1. Pointer to the next node in the master list.
2. Point to the linked list with this node as the head.

Examples are as follows:

  4 ->  9 -> 15 -> 19
  |     |     |     |
  7    13    18    28
  |           |     |
  8          21    37
  |                
  20               
  
 Implementation function flatten()，This function is used to flatten the linked list into a single linked list. For example, in the above linked list, the output linked list is
 
  4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37 

The topic requires us to combine the two-dimensional ordered linked list into a single linked list. Let's simplify the problem. Suppose that the main linked list has only two nodes, that is, the two-dimensional linked list becomes as follows.

 4 ->  9 
  |     |     
  7    13           Spin it         4 -> 7 -> 8 -> 20
  |               ---------->       |
  8                                 9 -> 13
  |                
  20   

Isn't this the merging of the two ordered linked lists we mentioned above? What if the master chain table has multiple nodes? We can use the idea of merging to merge one by one, as shown in the figure below.

Let's take a look at how the code is implemented.

class ListNode:
    def __init__(self, val=0, right=None, down=None):
        self.val = val
        self.right = right
        self.down = down

class Solution:
    def mergeTwoLists(self, l1, l2):
        #If one linked list is empty, the merged linked list is another
        if(l1==None):
            return l2
        if(l2==None):
            return l1

        if(l1.val<=l2.val):

            l1.down=self.mergeTwoLists(l1.down,l2)
            return l1
        else:
            l2.down=self.mergeTwoLists(l1,l2.down)
            return l2


    def flatten(self,root):
        if root== None or root.right == None:
            return root
        #Regard root - > right as an ordered single linked list,
        #Then merge by passing back
        return self.mergeTwoLists(root, self.flatten(root.right))

More algorithm solutions, please pay attention to the official account number, "programmer", welcome everyone to join.