extended_linked_list_solution.py

# Written by Eric Martin for COMP9021

from linked_list import *

class ExtendedLinkedList(LinkedList):
    def __init__(self, L = None):
        super().__init__(L)

    def rearrange(self, step):
        if step == 1:
            return
        node = self.head
        length = 1
        while node.next_node:
            node = node.next_node
            length += 1
        # We link the last node to the first one and create a loop.
        node.next_node = self.head
        node = self.head
        for j in range(step - 2):
            node = node.next_node
        new_head = node.next_node
        current_node = new_head
        node = current_node
        for i in range(length - 1):
            for j in range(step - 1):
                node = node.next_node
            current_node.to_be_next_node = node.next_node
            current_node = node.next_node
            node = current_node
        current_node.next_node = None
        self.head = new_head
        node = self.head
        for i in range(length - 1):
            node.next_node = node.to_be_next_node
            node = node.next_node