Question

Python Add your own implementation of the function rearrange_list

rearrange_list(linkedlist, number) returns the result of rearranging the nodes in linkedlist so that:

• all the nodes whose values are less than number are at the front
• all the nodes whose values are greater than number are at the rear
• any nodes whose values are equal to number are in the middle

For example, given the linked list represented by

linkedlist = -2 -> -3 -> -1 -> 2 -> 3 -> 0 -> 4 -> 1 -> 5

then

rearrange_list(linkedlist, 2) == -2 -> -3 -> -1 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5

You can see that all the numbers less than 2 now come before it, and all the numbers greater than 2 come after it. You can also see that the numbers maintain their relative position to each other, i.e. -2 and -3 and -1 don't change position relative to each other. This is an important characteristic, known as "stability". It also means that instead of requiring a full sort, you should be able to implement this algorithm in O(N) time.

You are given a simple Node class. Add your own implementation of the function rearrange_list (defined at the top level, not as part of the Node class)

Answer 1

ANSWER:

class Node:

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

def reverse(self):

prev = None

current = self.head

while(current is not None):

next = current.next

current.next = prev

prev = current

current = next

self.head = prev

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

self.head = new_node

def printList(self):

temp = self.head

while(temp):

if(temp.next!=None):

print(temp.data,end="->")

else:

print(temp.data,end="")

temp = temp.next

def populateList(self, number):

frontList=LinkedList()

rearList=LinkedList()

finalList=LinkedList()

found=False

temp = self.head

while(temp):

if temp.data==number :

found=True

else :

if temp.data<number :

frontList.push(temp.data)

else :

rearList.push(temp.data)

temp = temp.next

frontList.reverse()

rearList.reverse()

frontList.printList()

if found==True :

print("->"+str(number)+"->",end="")

rearList.printList()

num=input("Enter number of elements: ")

llist = LinkedList()

for x in range(int(num)):

val=input("Enter value: ")

llist.push(int(val))

llist.reverse()

print("\nGiven Linked List: ")

llist.printList()

print("\n\nEnter number to compare: ")

number=int(input())

print("\nFinal Result: ")

llist.populateList(number)

#SAMPLE OUTPUT

If you do not get anything in this solution,please put a comment and i will help you out.

Do not give a downvote instantly.It is a humble request.

If you like my answer,please give an upvote....Thank you.