Final Stretch, Day 9 of 10: I4G10DaysOfCodeChallenge

We have had hard challenges but this has to be the toughest so far. To solve this, I had to understand the linked list interfaces thoroughly, including understanding how to traverse a linked list before I could come up with an approach.

Problem Statement: Here's the link to the problem statement, please check it out so you can better follow along as I explain my approach.

My approach:

My approach basically involves looping through the input, lists, and each iteration returns a linked list which I would then traverse using this code construct below.

array = []
        for ll in lists:
            node = ll
            while node:
                array.append(node)
                node = node.next

On each traversal, I would get an iterableitem called node, similar to the i in for i in list assuming you were traversing a normal list/array. I would then append this listNode object, node, to an empty array.

The class definition of this listNode object is given as part of the initial code from the problem, highlighted here below

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

After appending the whole listNodes to this array. I then proceeded to sort this array, remember the array contains listNodes which isn't a comparable object.

for this sort() operation to be successful, I have to specify a listNode property that is comparable to use for the ordering. This is accomplished using this sort() construct below

array.sort(key=lambda node: node.val)

After this array is sorted, what remains is to convert the array( PS: which now contains sorted individual listNodes) back into a linked list.

This is achieved using the code construct below.

head = array[0]
        for i in range(1, len(array)):
            prev = array[i-1]
            node = array[i]
            prev.next = node
        return head

Heres the complete code below

class Solution(object):
    def mergeKLists(self, lists):

        # validate input
        if not lists:
            return None
        # shortcut, just return 1st linkedlist if only a single list
        if len(lists) == 1:
            return lists[0]

        # Create an empty array and fill it with all the elements
        #     from the LinkedLists
        array = []
        for ll in lists:
            node = ll
            while node:
                array.append(node)
                node = node.next
        # Verify elements were actually added to the array (LL could have all been empty)
        if not array:
            return None                

        # Sort the array
        array.sort(key=lambda node: node.val)

        # Create a new linked list from the array
        head = array[0]
        for i in range(1, len(array)):
            prev = array[i-1]
            node = array[i]
            prev.next = node
        return head