Merges two ordered lists

1. Topic description

Input two monotonically increasing lists, output the combined list of two lists, of course, we need the combined list to meet the monotonic rule.

Example 2.

There is no

3

Idea: Non-recursive

Compare the first node of two lists, and the smaller node is merged into the third list and moved forward one node.

Step 1 will result in a list being traversed first, or not

The third list tail points to the remaining list that has not been traversed

Returns the third list start

Recursive method:

4. A Java implementation

Non-recursive implementation: use an auxiliary header node: ListNode root = new ListNode(-1)

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} * /
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null) {return list2;
        }
        if (list2 == null) {return list1;
        }
        
        ListNode node = new ListNode(-1); // Save the header node
        ListNode root = node;
        
        while(list1 ! =null&& list2 ! =null) {if (list1.val < list2.val){
                node.next = list1;
                node = node.next; // Update the node to point to the next node
                list1 = list1.next;
            }else{ node.next = list2; node = node.next; list2 = list2.next; }}// It is possible that a list has some value left, for example, list 2 has some value left
        // 比如链表1： 1->2->4
        // list 2:3->5->6
        if(list1 == null){
            node.next = list2;
        }
        
        if (list2 == null){
            node.next = list1;
        }
        returnroot.next; }}Copy the code

Using a recursive implementation:

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null){ return list2; } if (list2 == null){ return list1; } ListNode ret = null; if (list1.val < list2.val){ ret = list1; ret.next = Merge(list1.next, list2); }else{ ret = list2; ret.next = Merge(list1, list2.next); } return ret; }}Copy the code

5. Python implementation

A simpler non-recursive implementation:

The non-recursive implementation merges two ordered lists
class Solution1:
    # return the merged list
    def Merge(self, pHead1, pHead2) :    
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        start = None 
        p = None 
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                print(pHead1.val)
                if start is None:
                    start = p = pHead1
                else:
                    p.next = pHead1
                    p = p.next # update node p
                pHead1 = pHead1.next Update the node of the ordered linked list
            else:
                if start is None:
                    start = p = pHead2
                else:
                    p.next = pHead2
                    p = p.next 
                pHead2 = pHead2.next 
        It is possible that a linked list will always have values left
        if not pHead1: # if the first list is empty
            p.next = pHead2
        else:
            p.next = pHead1
        return start 
Copy the code

Using a recursive implementation:

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: Def Merge(self, pHead1, pHead2): # write code here if not pHead1: Return pHead2 if not pHead2: return pHead1 if phead1. val <= phead2. val: ret = pHead1 ret.next = self.Merge(pHead1.next, pHead2) else: ret = pHead2 ret.next = self.Merge(pHead1, pHead2.next) return retCopy the code

If you found this article useful, please click “Watching”