CODEWITHSUNDEEP
pythonlinked-list
Qiang Super
Qiang Super

Reputation: 323

Rearrange a LinkedList, producing endless end points

I am now working on the problem of rearranging the linked list. The logic of the code feels right, but I encounter repeating the endless points of the linked list. I am not sure why, but feel more likely there is something wrong with the definition of the linked list. The question is:

Given the head of a Singly LinkedList, write a method to modify the LinkedList such that the nodes from the second half of the LinkedList are inserted alternately to the nodes from the first half in reverse order. So if the LinkedList has nodes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null, your method should return 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null.

Your algorithm should not use any extra space and the input LinkedList should be modified in-place.

Example 1:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> null Output: 2 -> 12 -> 4 -> 10 -> 6 -> 8 -> null

Example 2:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> null Output: 2 -> 10 -> 4 -> 8 -> 6 -> null

My approach is:

def rearrange_linkedlist(head):
    # find the middle as the separating point
    middle = middle_linkedlist(head)
    # reverse the second part
    second_head = reverse_linkedlist(middle)
    while head and second_head:
        following_1 = head.next 
        following_2 = second_head.next 
        head.next = second_head
        second_head.next = following_1
        head = following_1
        second_head = following_2

def middle_linkedlist(head):
    slow, fast = head, head 
    while fast and fast.next:
        slow = slow.next 
        fast = fast.next.next 
    return slow

def reserve_linkedlist(head):
    current = head 
    previous = None
    while current:
        following = current.next
        current.next = previous
        previous = current 
        current = following 
    return previous

The set up of the linked list:

from __future__ import print_function

class node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next 
    
    def print_list(self):
        temp = self
        while temp:
            print(str(temp.value) + ' ', end='')
            temp = temp.next 
        print()

def main():
    head = node(2)
    head.next = node(4)
    head.next.next = node(6)
    head.next.next.next = node(8)
    head.next.next.next.next = node(10)
    head.next.next.next.next.next = node(12)
    rearrange_linkedlist(head)
    head.print_list()
    
main()

And the result is:

2 12 4 10 6 8 8 8

with repeating 8. I am not sure what is wrong with it. Thanks for your help in advance.

Upvotes: 1

Views: 79

Answers (1)

Sash Sinha
Sash Sinha

Reputation: 22360

It might be beneficial to split up all three steps into different helper functions. I.e., currently, you only have a helper function for finding the middle and reversing a list. You should probably also have one for merging the two lists (this is where the issue is in your current code):

def rearrange_linkedlist(head):
    middle = find_middle(head)
    reversed_second_half = reverse_list(middle)
    merge_two_lists_inplace(head, reversed_second_half)


def find_middle(head):
    fast = slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow


def reverse_list(head):
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next  
    return prev


def merge_two_lists_inplace(l1, l2):
    while l1 and l2 and l2.next:
        l1.next, l1 = l2, l1.next
        l2.next, l2 = l1, l2.next

The issue with your code is that the end of the first half of the linked list points to the end of the reversed second half. On the final iteration of your merge loop the list looks like this:

2 -> 12 -> 4 -> 10 -> 6 -> 8 -> null
                      ^    ^
                     head  second_head

When you assign second_head.next = following_1 you're really assigning the final node to point to itself. Checking second_head.next in your loop condition terminates the loop when it's in the above state.

Upvotes: 1

Related Questions