Python3 Program to Rotate the sub-list of a linked list from position M to N to the right by K places

Last Updated : 31 Aug, 2022

Given a linked list and two positions ‘m’ and ‘n’. The task is to rotate the sublist from position m to n, to the right by k places. Examples:

Input: list = 1->2->3->4->5->6, m = 2, n = 5, k = 2 Output: 1->4->5->2->3->6 Rotate the sublist 2 3 4 5 towards right 2 times then the modified list are: 1 4 5 2 3 6 Input: list = 20->45->32->34->22->28, m = 3, n = 6, k = 3 Output: 20->45->34->22->28->32 Rotate the sublist 32 34 22 28 towards right 3 times then the modified list are: 20 45 34 22 28 32

Approach: For rotating the given sublist that extends from m to n element, move the list from (n-k+1)^th to n^th node to starting of sub-list to finish the rotation. If k is greater than size of sublist then we will take its modulo with size of sublist. So traverse through list using a pointer and a counter and we will save (m-1)^th node and later make it point to (n-k+1)^th node and hence bring (n-k+1)^th node to the start(front) of sublist. Similarly we will save m^th node and later make n^th node point to it. And for keeping rest of list intact we will make (n-k)^th node point to next node of n (maybe NULL). And finally we will get the k times right rotated sublist. Below is the implementation of the above approach:

Python3

# Python3 implementation of the above approach
import math
 
# Definition of node of linkedlist
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
 
# This function take head pointer of list, 
# start and end points of sublist that is 
# to be rotated and the number k and
# rotate the sublist to right by k places.
def rotateSubList(A, m, n, k):
    size = n - m + 1
 
    # If k is greater than size of sublist then 
    # we will take its modulo with size of sublist
    if (k > size):
        k = k % size
     
    # If k is zero or k is equal to size or k is
    # a multiple of size of sublist then list 
    # remains intact
    if (k == 0 or k == size):
        head = A
        while (head != None):
            print(head.data)
            head = head.next
         
        return
     
    link = None # m-th node
    if (m == 1) :
        link = A
     
    # This loop will traverse all node till
    # end node of sublist. 
    c = A # Current traversed node
    count = 0 # Count of traversed nodes
    end = None
    pre = None # Previous of m-th node
    while (c != None) :
        count = count + 1
 
        # We will save (m-1)th node and later
        # make it point to (n-k+1)th node
        if (count == m - 1) :
            pre = c
            link = c.next
         
        if (count == n - k) :
            if (m == 1) :
                end = c
                A = c.next
             
            else :
                end = c
 
                # That is how we bring (n-k+1)th
                # node to front of sublist.
                pre.next = c.next
             
        # This keeps rest part of list intact.
        if (count == n) :
            d = c.next
            c.next = link
            end.next = d
            head = A
            while (head != None) :
                print(head.data, end = " ")
                head = head.next
             
            return
         
        c = c.next
     
# Function for creating and linking new nodes
def push(head, val):
    new_node = Node(val)
    new_node.data = val
    new_node.next = head
    head = new_node
    return head
 
# Driver code
if __name__=='__main__': 
    head = None
    head = push(head, 70)
    head = push(head, 60)
    head = push(head, 50)
    head = push(head, 40)
    head = push(head, 30)
    head = push(head, 20)
    head = push(head, 10)
    tmp = head
    print("Given List: ", end = "")
    while (tmp != None) :
        print(tmp.data, end = " ")
        tmp = tmp.next
     
    print()
 
    m = 3
    n = 6
    k = 2
    print("After rotation of sublist: ", end = "")
    rotateSubList(head, m, n, k)
 
# This code is contributed by Srathore

Output:

Given List: 10 20 30 40 50 60 70 
After rotation of sublist: 10 20 50 60 30 40 70

Time complexity: O(N) where N is the size of the given linked list

Auxiliary space: O(1) because it is using constant space

Please refer complete article on Rotate the sub-list of a linked list from position M to N to the right by K places for more details!

GeeksforGeeks

Improve

C++ Program to Rotate the sub-list of a linked list from position M to N to the right by K places

Python3 Program to Rotate the sub-list of a linked list from position M to N to the right by K places

Python3

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?