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.
Input: 1->2->4, 1->3->4
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.