Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/21.html

21. Merge Two Sorted Lists

Level

Easy

Description

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->4

Solution

Create a dummyHead that occurs before the real head of the merged list. Use two pointers temp1 and temp2 to point to the current numbers in the two lists. Initially temp1 and temp2 point to the two lists’ heads respectively. While both temp1 and temp2 are in the lists, compare the numbers at temp1 and temp2, add the smaller number to the merged list, and move the corresponding pointer one step ahead. If one pointer reaches the end of the list, which is null, then add the numbers of the other pointer to the merged list. Finally, return dummyHead.next.

two pointers

big-o analysis

current = current.next; // now current is the new end node, but still pointing to next node

current.next = null; // @note: key, cut this node from l1 or l2

Code

  • 
    public class Merge_Two_Sorted_Lists {
    
    	/**
    	 * Definition for singly-linked list.
    	 * public class ListNode {
    	 *     int val;
    	 *     ListNode next;
    	 *     ListNode(int x) { val = x; }
    	 * }
    	 */
    
    	// Time complexity : O(N)
    	public class Solution {
    	    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    	        ListNode dummy = new ListNode(0);
    	        ListNode current = dummy;
    
    	        while (l1 != null || l2 != null) {
    	            int v1 = (l1 == null? Integer.MAX_VALUE : l1.val);
    	            int v2 = (l2 == null? Integer.MAX_VALUE : l2.val);
    
    	            if (v1 < v2) {
    	                current.next = l1;
    	                l1 = l1.next;
    	            } else {
    	                current.next = l2;
    	                l2 = l2.next;
    	            }
    
    	            current = current.next; // now current is the new end node, but still pointing to next node
    	            current.next = null; // @note: key, cut this node from l1 or l2
    	        }
    
    	        return dummy.next;
    	    }
    	}
    
    	public class Solution_extraSpace {
    	    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    	        ListNode dummy = new ListNode(0);
    	        ListNode current = dummy;
    
    	        while (l1 != null || l2 != null) {
    	            int v1 = l1 == null ? Integer.MAX_VALUE : l1.val;
    	            int v2 = l2 == null ? Integer.MAX_VALUE : l2.val;
    
    	            if (v1 < v2) {
    	                current.next = new ListNode(v1); // requires extra o(N) space
    	                l1 = l1.next;
    	            }
    	            else {
    	                current.next = new ListNode(v2);
    	                l2 = l2.next;
    	            }
    
    	            current = current.next;
    	        }
    
    	        return dummy.next;
    	    }
    	}
    }
    
    
    ############
    
    /**
     * 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 mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode();
            ListNode curr = dummy;
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    curr.next = list1;
                    list1 = list1.next;
                } else {
                    curr.next = list2;
                    list2 = list2.next;
                }
                curr = curr.next;
            }
            curr.next = list1 == null ? list2 : list1;
            return dummy.next;
        }
    }
    
  • // OJ: https://leetcode.com/problems/merge-two-sorted-lists/
    // Time: O(A + B)
    // Space: O(1)
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
            ListNode head, *tail = &head;
            while (a && b) {
                if (a->val <= b->val) {
                    tail->next = a;
                    a = a->next;
                } else {
                    tail->next = b;
                    b = b->next;
                }
                tail = tail->next;
            }
            tail->next = a ? a : b;
            return head.next;
        }
    };
    
  • # without ops after while loop
    class Solution:
        def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode()
            current = dummy
            while list1 or list2:
                v1 = list1.val if list1 else float('inf')
                v2 = list2.val if list2 else float('inf')
    
                if v1 < v2:
                    current.next = list1
                    list1 = list1.next
                else:
                    current.next = list2
                    list2 = list2.next
                current = current.next
    
            return dummy.next
    
    ############
    
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def mergeTwoLists(
            self, list1: Optional[ListNode], list2: Optional[ListNode]
        ) -> Optional[ListNode]:
            dummy = ListNode()
            curr = dummy
            while list1 and list2:
                if list1.val <= list2.val:
                    curr.next = list1
                    list1 = list1.next
                else:
                    curr.next = list2
                    list2 = list2.next
                curr = curr.next
            curr.next = list1 or list2
            return dummy.next
    
    """
            curr.next = list1 or list2
    
    better than:
    
            if list1:
                current.next = list1
            if list2:
                current.next = list2
    
    
    """
    
    
  • /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    	dummy := &ListNode{}
    	curr := dummy
    	for list1 != nil && list2 != nil {
    		if list1.Val <= list2.Val {
    			curr.Next = list1
    			list1 = list1.Next
    		} else {
    			curr.Next = list2
    			list2 = list2.Next
    		}
    		curr = curr.Next
    	}
    	if list1 != nil {
    		curr.Next = list1
    	} else {
    		curr.Next = list2
    	}
    	return dummy.Next
    }
    
  • /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */
    
    function mergeTwoLists(
        list1: ListNode | null,
        list2: ListNode | null,
    ): ListNode | null {
        if (list1 == null || list2 == null) {
            return list1 || list2;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    
    
  • /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} list1
     * @param {ListNode} list2
     * @return {ListNode}
     */
    var mergeTwoLists = function (list1, list2) {
        const dummy = new ListNode();
        let curr = dummy;
        while (list1 && list2) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        curr.next = list1 || list2;
        return dummy.next;
    };
    
    
  • # Definition for singly-linked list.
    # class ListNode
    #     attr_accessor :val, :next
    #     def initialize(val = 0, _next = nil)
    #         @val = val
    #         @next = _next
    #     end
    # end
    # @param {ListNode} list1
    # @param {ListNode} list2
    # @return {ListNode}
    def merge_two_lists(list1, list2)
        dummy = ListNode.new()
        cur = dummy
        while list1 && list2
            if list1.val <= list2.val
                cur.next = list1
                list1 = list1.next
            else
                cur.next = list2
                list2 = list2.next
            end
            cur = cur.next
        end
        cur.next = list1 || list2
        dummy.next
    end
    
  • /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int val=0, ListNode next=null) {
     *         this.val = val;
     *         this.next = next;
     *     }
     * }
     */
    public class Solution {
        public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode();
            ListNode cur = dummy;
            while (list1 != null && list2 != null)
            {
                if (list1.val <= list2.val)
                {
                    cur.next = list1;
                    list1 = list1.next;
                }
                else
                {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = list1 == null ? list2 : list1;
            return dummy.next;
        }
    }
    
  • // Definition for singly-linked list.
    // #[derive(PartialEq, Eq, Clone, Debug)]
    // pub struct ListNode {
    //   pub val: i32,
    //   pub next: Option<Box<ListNode>>
    // }
    //
    // impl ListNode {
    //   #[inline]
    //   fn new(val: i32) -> Self {
    //     ListNode {
    //       next: None,
    //       val
    //     }
    //   }
    // }
    impl Solution {
        pub fn merge_two_lists(
            list1: Option<Box<ListNode>>,
            list2: Option<Box<ListNode>>,
        ) -> Option<Box<ListNode>> {
            match (list1, list2) {
                (None, None) => None,
                (Some(list), None) => Some(list),
                (None, Some(list)) => Some(list),
                (Some(mut list1), Some(mut list2)) => {
                    if list1.val < list2.val {
                        list1.next = Self::merge_two_lists(list1.next, Some(list2));
                        Some(list1)
                    } else {
                        list2.next = Self::merge_two_lists(Some(list1), list2.next);
                        Some(list2)
                    }
                }
            }
        }
    }
    
    

All Problems

All Solutions