Original link:

https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

Topic describes

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.

Example:

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

What is the meaning of the passage?

There are two linked lists in which the elements are arranged in order (usually from smallest to largest). The required result is a linked list containing the elements of the given two lists, also in order.

You need to be familiar with list structure and list traversal.

Train of thought

The current value of the two lists is compared. The smaller value is the element of the new list. The smaller value is then moved to the next element, and the larger value is the current element. Continue iterating, repeating the above steps until the list is iterated. So you get a new ordered list. A few things to note:

  • For this problem, it is best to create a header as an aid, so that you do not have to determine whether the new list’s header is l1 or L2.
  • At the end of the loop, there’s usually a list that’s done first. You can then concatenate another list without going through the concatenation.

Code (Python)

    def mergeTwoLists(self, l1, l2):
        """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """
        # check if a linked list is empty
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        
        Create a new header as a helper
        head = ListNode(0)
        #currentNode is the currentNode of the new list
        currentNode = head
        
        # Loop through two lists, then join them together to form a new list
        while(l1 or l2):
            
            If a list has already been traversed, do not continue
            if l1 == None:
                currentNode.next = l2
                print "l2=",l2.val
                break
            if l2 == None:
                currentNode.next = l1
                print "l1=",l1.val
                break

            # Judge size
            if l1.val < l2.val:
                # Splice new linked list
                currentNode.next = l1
                
                currentNode = currentNode.next
                print "l1=",l1.val
                l1 = l1.next
            else:
                currentNode.next = l2
                
                currentNode = currentNode.next
                print "l2=",l2.val
                l2 = l2.next
                
        return head.next
Copy the code

Modest words forgotten language

Currently, I only know a little Python syntax, so I will not optimize the syntax, and the overall code style will try to be consistent with THE C language.