Reverse and Right Shift SLL
Submit solution
Python
Points:
10 (partial)
Time limit:
8.0s
Memory limit:
64M
Authors:
Problem type
Allowed languages
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