Highlights:

Description:

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Lessons Learned:

In brushing off the rust from my coding skills, this was a pleasant way to ease back into a rudimentary Data Structure. Singly-Linked Linked Lists are traversable one-way (and one-way only!). The first solution that came to mind was to create a new Linked List and simply copy whichever value was higher from linked list l1 or l2 (inspiration came from MergeSort).

However, the description clearly states that the new list should be made by splicing together the existing nodes, so rather than create a new Linked List, I had to work with what was given.

The algorithm below first determines which node should be the starting point (even going to far as to validate that there are even contents in either Linked List; something I didn’t check for initially until I tried submitting and encountered that as an edge case). Then, with a starting node (head) determined, I use a while-loop to go through the Linked Lists. Within the loop the algorithm looks at the value of the next node in the current Linked List, the value of the next node in the other Linked List, and then decides which one it should thread to.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        #if either/both lists are not populated
        if l1 is None and l2 is None:
            return l1
        elif l1 is None:
            head = l2
            node = head
            otherNode = l1
        elif l2 is None:
            head = l1
            node = head
            otherNode = l2
        
        #Determine which LinkedList should start
        elif l1.val <= l2.val:
            head = l1
            node = l1
            otherNode = l2
            otherNodeNext = l2.next
        else:
            head = l2
            node = l2
            otherNode = l1
            otherNodeNext = l1.next 
        
        while node is not None:
            
            if node.next is None and otherNode is None:
                break
            elif node.next is None:
                placeHolder = otherNode
                otherNode = node.next
                node.next = placeHolder
                node = node.next
                continue
            
            #if current node value is the same as the next in chain OR...
            if ((node.val == node.next.val) or 
                (otherNode is None) or (
                (node.val != otherNode.val) and
                (node.val != node.next.val) and
                (node.next.val <= otherNode.val))):
                node = node.next
                
            else:
                placeHolder = otherNode
                otherNode = node.next
                node.next = placeHolder
                node = node.next
        
        return head
                

• ← Previous Post
• Next Post →