2: Merge Two Sorted Lists

Merges two ordered lists into a new ordered list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code

Answer:

Both iteration and recursion work. The value of each node of the two linked lists is compared in turn, and the node with the smaller value is taken out and added to the end of the new linked list. Then continue to compare the two lists until one list is traversed and all the remaining nodes of the other list are directly added to the new list. Its logic is as follows:

Original linked list: 1->2->4-> NULL, 1->3->4->5->6-> NULL Compare node values and take out each head node: 1 = 1 If the value is the same, take out one node 1 to form a new linked list: 1 At this time, the original linked list: 2->4-> NULL, 1->3->4->5->6-> NULL

Compare the value of head node: 2 >1 Take out 1 node and add it to the end of the new list: 1->1

Compare the value of the head node: 2 < 3 Take out 2 nodes and add them to the end of the new list: 1->1->2

. And so on until one of the original lists is empty:

New list: 1->1->2->3->4 When one of the original lists is empty, add another one to the end of the new list: 1->1->2->3->4->4->5->6-> NULL

Iterative method:

Iteration method needs to pay attention to: first judge whether the original linked list is empty; Compare the value of the first node of the original list and choose the smaller one as the head node of the new list. Then follow the above logic.

If you add a virtual node as the head node, this condition is not required, but the next node of the virtual node should be returned.

Java:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);// Create a virtual head node
        ListNode cur = head;// The current node points to the virtual head node
        while(l1 ! =null&& l2 ! =null) {// The loop condition is that the linked list is not empty
            if (l1.val < l2.val) {// Compare the size of the header node
                cur.next = l1;// The current node is connected to the one with the smaller value
                l1 = l1.next;// Refresh the original list head node
                cur = cur.next;// Refresh the current node
            } else{ cur.next = l2; l2 = l2.next; cur = cur.next; }}if (l1 == null) cur.next = l2;// Select another, non-empty, link to the end of the new list
        else cur.next = l1;
        return head.next;// Returns the next node of the virtual head node, the real head node}}Copy the code

Python3:

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(- 1)
        cur = head;
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = l2
                cur = cur.next
                l2 = l2.next
        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return head.next

Copy the code

Recursive method:

The recursive baseline condition is: one of the original linked lists encounters an empty node. The return value is: the head node of the rest of another list.

Recursively determine the size of the value of the head node, take the small node to add to the new list. Pass the rest of the list back to the recursive function.

Java:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;// Baseline conditions
        if (l2 == null) return l1;// Baseline conditions
        ListNode head;
        if (l1.val <= l2.val) {// Select nodes with smaller values
            head = l1;// Refresh the head node
            head.next = mergeTwoLists(l1.next, l2);// The rest of the list is passed to the recursive function as arguments
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        returnhead; }}Copy the code

Python3:

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val <= l2.val:
            head = l1
            head.next = self.mergeTwoLists(l1.next, l2)
        else:
            head = l2
            head.next = self.mergeTwoLists(l1, l2.next)
        return head

Copy the code

Welcome to wechat. Common name: Love to write bugs