How do you populate values into a class in python-CodePudding

I have a code that works for merging 2 linked lists for leetcode. However, upon testing it, I am facing a bottleneck. How do I populate the ListNode with a list? the following outputs just 1 whatever, not the merged linked list.

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        return str(self.val)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        place_holder = ListNode()
        tmp = place_holder

        while list1 and list2:
            if list1.val < list2.val:
                tmp.next = list1
                list1 = list1.next
            else:
                tmp.next = list2
                list2 = list2.next
            tmp = tmp.next

        if list1 is None:
            tmp.next = list2

        if list2 is None:
            tmp.next = list1

        return place_holder.next

#input the two integer lists
l1 = [1, 2, 4]
l2 = [1, 3, 4]

list1 = ListNode(l1[0])
list2 = ListNode(l2[0])

list_result = Solution().mergeTwoLists(list1, list2)
print(list_result)

CodePudding user response：

Fix your __str__ so it prints the whole linked list:

    def __str__(self):
        s = f"({str(self.val)})"
        if self.next:
            s  = f" -> {self.next}"  # be careful not to build any circular lists...
        return s

and now you can see the actual result of your merge function:

(1) -> (1)

which is 100% correct (at least for these inputs) because you merged the lists (1) and (1).

Writing a function that lets you turn a list of multiple numbers into a single linked list will make it easier to test this logic with longer inputs. One option would be to just do this in your ListNode constructor:

from typing import List, Optional, Union

class ListNode:
    def __init__(self, val: Union[int, List[int]] = 0) -> None:
        vals = val if isinstance(val, list) else [val]
        self.val = vals[0]
        self.next = ListNode(vals[1:]) if vals[1:] else None

    def __str__(self) -> str:
        s = f"({str(self.val)})"
        if self.next:
            s  = f" -> {self.next}"
        return s

Now you can do:

#input the two integer lists
l1 = [1, 2, 4]
l2 = [1, 3, 4]

list1 = ListNode(l1)
list2 = ListNode(l2)

list_result = Solution().mergeTwoLists(list1, list2)
print(list_result)  # (1) -> (1) -> (2) -> (3) -> (4) -> (4)

CodePudding user response：

You need a way to convert a regular Python list to a linked list. Your nodes are initialized with one integer each (never mind that it came from l1 and l2), so they can't grow any next elements by themselves. To fix it, add a static method to ListNode that accepts a list:

class ListNode:

    @static
    def fromList(lst):
        if not lst:
            return None

        return ListNode(lst[0], next=ListNode.fromList(lst[1:]))

This will recursively convert a Python list into a linked list. Then you can initialize your linked lists like this:

list1 = ListNode.fromList(l1)
list2 = (same)

CodePudding user response：

You need to convert your list value into a List value. (I recommend using separate classes for nodes and the list that consists of those nodes.)

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        return str(self.val)


class List:
    def __init__(self, values=None):
        # Dummy node that is independent of any actual
        # data. You can store the length (or really, any
        # metadata you like) in the dummy node.
        self.head = ListNode(0)
        if values is None:
            values = []

        for x in values:
            self.append(x)

    def append(self, value):
         ...


list1 = List(l1)
list2 = List(l2)

You'll need to implement List.append, and possibly some other methods. It's better to do all the pointer wrangling in List itself and to provide methods for mergeTwoLists to construct the resulting List.