How do I calculate the midpoint of a linked list so that the first half of the list includes the extra node when the length of the list is odd?

Question

>>> s1, s2 = x.split()
>>> s1
Head:Node(-7.5)
Tail:Node(3.75)
List:-7.5 -> 0 -> 1 -> 3 -> 3.75
>>> s2
Head:Node(4)
Tail:Node(9.78)
List:4 -> 5 -> 8.76 -> 9.78

This is the test case I need to pass, I have written some code but it does not return the two sublists I wanted. add is a function I wrote which adds the value to a linked list

These are the initial constructors of the class

def __init__(self):   # You are not allowed to modify the constructor
    self.head=None
    self.tail=None

def __str__(self):   # You are not allowed to modify this method
    temp=self.head
    out=[]
    while temp:
        out.append(str(temp.value))
        temp=temp.next
    out=' -> '.join(out) 
    return f'Head:{self.head}\nTail:{self.tail}\nList:{out}'

__repr__=__str__


def isEmpty(self):
    return self.head == None

def __len__(self):
    count=0
    current=self.head
    while current:
        current=current.next
        count+=1
    return count

This is my attempted solution, I cannot use any break or continue statements, swap data between nodes or to copy data from the linked lists into another structure such as a Python list or using any Python built-in copy methods.

def split(self):
    # find the half length of the list
    mid = round(len(self) // 2)
    # create two lists - to store both halves
    left = SortedLinkedList()
    right = SortedLinkedList()
    # take reference to head
    current = self.head
    # loop for mid number of times
    for i in range(mid):
        # add value of current node to left list
        left.add(current.value)
        # advance current
        current = current.next
    # now loop as long as current is not None
    while current:
        # add value of current node to right list
        right.add(current.value)
        # advance current
        current = current.next
    # return both lists
    return left, right

Failed examples:

File "c:\python\CMPSC 132 sp\LAB4.py", line 44, in __main__.SortedLinkedList
Failed example:
    s1
Expected:
    Head:Node(-7.5)
    Tail:Node(3.75)
    List:-7.5 -> 0 -> 1 -> 3 -> 3.75
Got:
    Head:Node(-7.5)
    Tail:Node(3)
    List:-7.5 -> 0 -> 1 -> 3
Trying:
    s2
Expecting:
    Head:Node(4)
    Tail:Node(9.78)
    List:4 -> 5 -> 8.76 -> 9.78
**********************************************************************
File "c:\python\CMPSC 132 sp\LAB4.py", line 48, in __main__.SortedLinkedList
Failed example:
    s2
Expected:
    Head:Node(4)
    Tail:Node(9.78)
    List:4 -> 5 -> 8.76 -> 9.78
Got:
    Head:Node(3.75)
    Tail:Node(9.78)
    List:3.75 -> 4 -> 5 -> 8.76 -> 9.78

`round` sometimes rounds up and sometimes rounds down. It seems you need to always round up. — mkrieger1, Mar 06 '23 at 00:17
Yeah, is there a way I can do that? I'm trying to use floor division to round up, but it does not seem to work. — Toodles, Mar 06 '23 at 00:22
Does this answer your question? [How do you round UP a number?](https://stackoverflow.com/questions/2356501/how-do-you-round-up-a-number) — mkrieger1, Mar 06 '23 at 00:24
Perhaps `mid = (len(self) + 1) // 2`? That will always round up — Nick, Mar 06 '23 at 00:28
math.ceil does pass the case, however I'm not allowed to import math in this case — Toodles, Mar 06 '23 at 00:29
I see. Maybe you can use one of the at least 2 other solutions that don't use `math.ceil`. — mkrieger1, Mar 06 '23 at 00:30
now I remember that adding +1 will always roundup without importing the math module. — Toodles, Mar 06 '23 at 00:31

score 0 · Answer 1 · answered Mar 06 '23 at 04:53

You could have two pointers advancing through the linked list with one stepping by one and the other advancing by two. When the faster one reaches the end of the list, the slow pointer will be at the half point. Wether you include the extra odd position or not is a matter of ordering the increments.

slow = L.head
fast = L.head
while fast:
   slow = slow.next
   fast = fast.next
   if fast : 
      fast = fast.next

At the end of the loop, slow will only have passed through half the list. you can use this to either split the list by manipulating pointers or to build a separate list as you go.

How do I calculate the midpoint of a linked list so that the first half of the list includes the extra node when the length of the list is odd?

1 Answers1