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.