rotate_the_list.py

class Node(object):

    __slots__ = ['key', 'next']

    def __new__(cls, key):
        obj = object.__new__(cls)
        obj.key = key
        obj.next = None
        return obj

class SinglyLinkedList(object):

    __slots__ = ['head', 'last_node', 'node_count']

    def __new__(cls):
        obj = object.__new__(cls)
        obj.head = None
        obj.node_count = 0
        obj.last_node = None
        return obj
    
    def append(self, key):
        new_node = Node(key)
        if  self.head is None:
            self.head = new_node
            self.last_node = self.head
        else:
            self.last_node.next = new_node
            self.last_node = new_node
        self.node_count += 1
    
    def search(self, key):
        walk = self.head
        prev_node, del_node = None, None
        while walk is not None and walk.key != key:
            prev_node = walk
            walk = walk.next
        del_node = walk
        return prev_node, del_node
        
    def delete(self, key):
        prev_node, del_node = self.search(key)
        if del_node is not None:
            if prev_node is not None:
                prev_node.next = del_node.next
            del del_node
            self.node_count -= 1
            return True
        return False
    
    def __str__(self):
        string = ""
        walk = self.head
        while walk is not None:
            string += str(walk.key) + " "
            walk = walk.next
        return string
    
    def rotate(self, k):
        if self.node_count > 0:
            k = k % self.node_count
            if k > 0:
                while k > 0:
                    prev_node, _ = self.search(self.last_node.key)
                    self.last_node.next = self.head
                    self.head = self.last_node
                    prev_node.next = None
                    self.last_node = prev_node
                    k -= 1
            else:
                k = -k
                while k > 0:
                    new_head = self.head.next
                    self.last_node.next = self.head
                    self.head.next = None
                    self.last_node = self.head
                    self.head = new_head

def merge(left, right, combined):
    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i].key <= right[j].key:
            combined[k] = left[i]
            i += 1
        else:
            combined[k] = right[j]
            j += 1
        k += 1
    
    while i < len(left):
        combined[k] = left[i]
        i += 1
        k += 1
    
    while j < len(right):
        combined[k] = right[j]
        j += 1
        k += 1

def merge_sort_helper(addr_list):
    if len(addr_list) <= 1:
        return addr_list
    
    size = len(addr_list)
    left = [addr_list[i] for i in range(size//2)]
    right = [addr_list[i] for i in range(size//2, size)]
    merge_sort_helper(left)
    merge_sort_helper(right)
    merge(left, right, addr_list)
    del left
    del right

def merge_sort(linked_list_1):
    addr_list = []
    walk = linked_list_1.head
    while walk is not None:
        addr_list.append(walk)
        walk = walk.next
    merge_sort_helper(addr_list)
    for i in range(len(addr_list) - 1):
        addr_list[i].next = addr_list[i+1]
    if addr_list:
        addr_list[-1].next = None
        linked_list_1.head = addr_list[0]
        linked_list_1.last_node = addr_list[-1]

import sys
def read():
    return map(int, sys.stdin.readline().strip().split())

singly_linked_list = SinglyLinkedList()
del_linked_list = SinglyLinkedList()
Q1 = int(input())
for _ in range(Q1): # performing the first Q1 queries
    qtype, x = read()
    if qtype == 1:
        singly_linked_list.append(x)
    else:
        status = singly_linked_list.delete(x)
        if status:
            del_linked_list.append(x)
    print(str(singly_linked_list))

Q2 = int(input())
k_total = 0
for _ in range(Q2): # performing rotation queries
    k = int(input())
    k_total += k
singly_linked_list.rotate(k_total)
print(str(singly_linked_list))
merge_sort(singly_linked_list)
merge_sort(del_linked_list)
if singly_linked_list.node_count > 0:
    singly_linked_list.last_node.next = del_linked_list.head
merge_sort(singly_linked_list)
print(str(singly_linked_list))