Reverse and Right Shift SLL


Submit solution

Points: 10 (partial)
Time limit: 8.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
Python

Problem Definition

Singly Linked List is a linear data structure with the following functions

I - Checks whether linked list is empty S - Size of linked list IF - IL - IA x y - Insert y after x in the linked list R - reverse the linked list RS k - right shifts the elements of linked list by k times. DF - deletes first element DL - deletes the last element

In this problem you are requested to implement three functions. 1-Insert After, 2-Reverse and 3-Right Shift. Code template for the same is given below.

Sample Input:

10

I

IF 1

IF 2

IF 3

IL 4

S

DF

IA 1 5

R

RS 2

Sample Output:

True

1

2 1

3 2 1

3 2 1 4

4

2 1 4

2 1 5 4

4 5 1 2

1 2 4 5

Code Template

class SLList:

     class node:
         def __init__(self,data):
               self.element = data
               self.next = None

     def __init__(self):
          self.head = self.node(None)
          self.sz = 0


     def insertLast(self,data):
          u=self.node(data)
          if (self.head.element == None):
               self.head.element = u.element
               self.sz+=1
          else:
               curnode = self.head
               while (curnode.next!=None):
                    curnode = curnode.next
               curnode.next = u
               self.sz+=1
          return

     def insertFirst(self,data):
          u=self.node(data)
          if (self.head.element == None):
               self.head.element = u.element
               self.sz+=1
          else:
               u.next = self.head
               self.head = u
               self.sz+=1
          return

     def insertAfter(self,u,v): #insert v after u node.
          x=self.node(u)
          y=self.node(v)
          #to be finished.
          return

     def deleteFirst(self):

          if self.size()!=0:
               if self.head.next == None:
                   self.head.element = None
                   #self.sz= self.sz-1
               else:
                   temp = self.head
                   self.head = self.head.next
                   del temp
               self.sz = self.sz-1
          return

     def deleteLast(self):
          if self.size()!=0:
               if self.head.next == None:
                   self.head.element = None
               else:
                   curnode = self.head
                   while (curnode.next.next != None):
                        curnode = curnode.next
                   temp = curnode.next
                   curnode.next = None
                   del temp
               self.sz = self.sz-1
          return


     def printList(self):
         if (self.isEmpty()):
            print ("Linked List Empty Exception")
         else:
          tnode = self.head
          while tnode!= None:
               print(tnode.element,end=" ")
               tnode = tnode.next
          print(" ")
          return

     def findNode(self, val):
          curnode = self.head
          while curnode!=None:
               if curnode.element == val:
                    return curnode
               curnode = curnode.next
          return None

     def isEmpty(self):
          return self.sz==0

     def size(self):
          return self.sz

     def reverse(self):
          #your code here...
          return
     def rightshift(self,k):
          #your code here...
          return  
def testSLL():
    sll = SLList()
    inputs=int(input())
    while inputs>0:
        command=input()
        operation=command.split()
        if(operation[0]=="S"):
            print(sll.size())
        elif(operation[0]=="I"):
            print(sll.isEmpty())
        elif(operation[0]=="IF"):
            sll.insertFirst(int(operation[1]))
            sll.printList()
        elif(operation[0]=="IL"):
            sll.insertLast(int(operation[1]))
            sll.printList()
        elif(operation[0]=="DF"):
            sll.deleteFirst()
            sll.printList()
        elif(operation[0]=="DL"):
            sll.deleteLast()
            sll.printList()
        elif(operation[0]=="IA"):
            sll.insertAfter(int(operation[1]), int(operation[2]))
            sll.printList()
        elif(operation[0]=="R"):
            sll.reverse()
            sll.printList()
        elif(operation[0]=="RS"):
            sll.rightshift(int(operation[1]))
            sll.printList()

        inputs-=1


def main():
    testSLL()

if __name__ == '__main__':
    main()

Comments

There are no comments at the moment.