21. Merge Two Sorted 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->4

code

We need to traverse both lists until we reach the end of one linked list.
We will keep two pointers that serve as the current pointer of the two list. They are inited as the head of the two list. We also need one pointer that serve as the current pointer of the new list, it will initialized as dummy node since we don’t know which node will be the actual head. In each iteration, we will point the next of new_cur to the smaller of the two current pointer and move the smaller of the current pointer forward.
When one current pointer reaches the end, that means we have put all nodes of one list into the new list. We can finish off by appending the remaining list to the cur_ptr.next.
It will let us terminate the while loop earlier and save us from appending the None ourselves.

and in each iteration, we will point the

    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode

        """

        new_dummy_head = ListNode(1)
        cur_ptr = new_dummy_head

        while l1 and l2:
            if l1.val < l2.val:
                cur_ptr.next = l1
                l1 = l1.next
            else:
                cur_ptr.next = l2
                l2 = l2.next
            cur_ptr = cur_ptr.next

        if not l1:
            cur_ptr.next = l2
        if not l2:
            cur_ptr.next = l1

        return new_dummy_head.next

Use of dummy head

We used dummy head again. It solves several problems:

Leaving space for the head node without knowing which node will be the head.

Without it, we need to first compare which node is smaller and use the smaller node as the head. With dummy head, we can integrate it into the while loop.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax