Data structures in Python, Series 1.5: Linked Lists : portion reversing

Reverse a Linked List in groups of given size : 

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev. See this post for reversing a linked list.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */

Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3
Output:  3->2->1->6->5->4->8->7->NULL.

Inputs:   1->2->3->4->5->6->7->8->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL.

# Firt of all make a node class for every future node to be shaped like .
class node():
    def __init__(self,data,nextnode = None):
        self.data = data
        self.nextnode = nextnode
#now make a class with the all the operations that can be operated in a list
#remember do get a __init__ as this will be used to initiate the default values for the instance in main

class linkedlist():
    def __init__(self):
        self.head = None
        self.data = 0
        self.size = 0
    def addnode(self,data):
        self.data = data
        new = node(data,self.head)
        self.head = new
        self.size +=1
    def __print__(self):
        cur = self.head
        while cur:
            print(str(cur.data),end = '>>')
            cur = cur.nextnode
        print('None')

    def reveser_portions(self,head,k):
        current = head
        Next = None
        prev = None
        count = 0
        while(current is not None and count < k ):
            Next = current.nextnode
            current.nextnode = prev
            prev = current
            current = Next
            count +=1
        if Next is not None:
            head.nextnode = self.reveser_portions(Next,k)
        return prev

if __name__ == '__main__':
    lis1 = linkedlist()
    for i in range(int(input('enter the number of elements to be inserted'))):
        lis1.addnode(int(input('enter the value')))
   
    #lis.deletenodeposition(1)
    lis1.__print__()

    lis1.head = lis1.reveser_portions(lis1.head,2)
    lis1.__print__()

ref : geeks for geeks

Comments

Popular Posts