Home > Back-end >  Calling a linked list
Calling a linked list

Time:07-11

I'm new to programming, so excuse the possibly stupid question.

I'm doing leetcodes and I got to the linked lists. I think I understand them okay, it's just that I don't know how to test my code/call my function(?)

Problem I'm working on

Here's my code, I know it works since I uploaded it onto leetcode, but I would still like to be able to run it on my machine.

class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

I guess I have two different problems:

  • the "Optional[ListNode]) -> Optional[ListNode]:" part
  • and the actual calling of the function
  1. Some questions before used the "typing" module functions like "List", so I would simply import them and they wouldn't be a problem. But I'm not really sure what to do here

  2. To check my solutions, I write a short piece of code that I can put example inputs into

    Solution = Solution() print(Solution.middleNode(head = [1,2,3,4,5,6]))

But isn't the "head" there, just a normal list? Do I have to create an extra function separately to create the "links". I've seen the creation of a linked list done by calling a function every time you want to add a new node. So would I use a for loop to add my example case?

CodePudding user response:

I think the problem on LeetCode is poorly worded. head = [1,2,3,4,5] is not really a head as it should only refer to the first item in the list - there seems to be a bit of hidden boilerplate code that creates a linked list from input list and an output list from output node.

Here's an example code that works similiar to the LeetCode task.

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow        

inp = [1,2,3,4,5,6]

next = None

for i in reversed(inp):
    next = ListNode(i, next) # next points to head at the end of the loop

res = Solution().middleNode(next)

out = []

while res:
    out.append(res)
    res = res.next

print([o.val for o in out])

CodePudding user response:

to make your code work on your machine you have to implement a couple of things: First, for your first answer, you have to implement the class ListNode given at the top of the leetcode-page:

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

The you import "Optional" from typing:

from typing import Optional

Then you have the prerequisites for your code. You have to initialise the class, as you have mentioned. The only problem here is, that your variable has the same name as your class, what could cause trouble later. To finish, you have to call your function as you already did, with one little difference: This function has to be called with "head" as a variable of type ListNode, not List, and gives you back a variable of the type ListNode.

In a nutshell, this would be my solution (of course you can and as much ListNodes as you want):

from typing import Optional


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

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

# Initialise class
s = Solution()

# Defining nodes of the list, assigning always the next node.
seven = ListNode(7)
six = ListNode(6, next=seven)
five = ListNode(5, next=six)
four = ListNode(4, next=five)
three = ListNode(3, next=four)
two = ListNode(2, next=three)
one = ListNode(1, next=two)

# Calling your function (with "one" as your head node of the list)
# NOTE: As this gives you back an attribute of type ListNode, you have to access the "val" attribute of it to print out the value.
print(s.middleNode(one).val)

CodePudding user response:

well if you looking for internal boilerplate, below is code for that.

here you need to create classes for nodes, linked list and solutions,.

then with the given number, you need to create a linkedlist object. this above part is done in leetcode by themself and this object is passed to class Solution method middleNode, where OP code run and give result. next once output is got it is compared with existing solution

# Node class for individual nodes
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
# linked list class, to create a linked list of the list nodes        
class LinkedList:
    def __init__(self):
        self.head = None
    # adding a node element to linked list
    def add(self, node):
        if self.head is None:
            self.head = node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = node
            curr = node
    # printing element of existing linked list
    def print_ll(self):
        curr= self.head
        while curr:
            print(curr.val)
            curr= curr.next

# leetcode solution class
class Solution:
        def middleNode(self, head) :
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        
# value with which we create list nodes
values = [1,2,3,4,5,6,7,8,9,10]

ll = LinkedList() # create a linked list class object
for i in values:
    node =  ListNode(i) # creating a list node
    ll.add(node) # adding list node to linked list
#ll.print_ll() # printing linked list

x = Solution().middleNode(ll.head) # passing linked list object to leetcode solution method and getting result

while x: # printing result 
    print(x.val)
    x=x.next

CodePudding user response:

head is pointing to the first element in the list. You should go through the topic "Pointers in C", you'll understand more.

Python uses a lot of shorthand for declaring and defining.

  • Related