Merge Two Sorted Linked Lists

class Solution(object): def merge(self, one, two): """ input: ListNode one, ListNode two return: ListNode """ # write your solution here if (one == None and two == None): return one elif (one == None and two != None): return two elif (one != None and tw0 == None): return one else: ptr1 = one ptr2 = two # construct the first node if (ptr1.val <= ptr2.val): new_node = ListNode(ptr1.val) ptr1 = ptr1.next else: new_node = ListNode(ptr2.val) ptr2 = ptr2.next head = new_node ptr3 = head # now traverse the two lists... while(ptr1 != None and ptr2 != None): # make a new node if (ptr1.val <= ptr2.val): new_node = ListNode(ptr1.val) ptr1 = ptr1.next else: new_node = ListNode(ptr2.val) ptr2 = ptr2.next # attach the node to the result list ptr3.next = new_node ptr3 = ptr3.next # now one of the list is empty... # attach the remaining part of the list... if (ptr1 == None): ptr3.next = ptr2 else: ptr3.next = ptr1 return head
One pass! Except for a typo.

Might have excessive error check...

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.