Question

given a linked list and a value x partition it such that all nodes less than x come before nodes greater than or equal to x. you should preserve the original relative order of the nodes in each of the two partitions. for example given 1->4->3->2->5->2 and x = 3 return 1->2->2->4->3->5.

Answer 1

sorry for the rank information fhxjdkfjebbejxjfjrbbebdfffbd ffjgbdhdhxiidrfcufi8dffggggghhgv gjkddkjfudidj vufifnfkkfkdkeowososodidifi ggtkflekejejrjfjfghjfii gejdido, gjrofidieuyerriiehejrrjdjfjrhurgi, I have jrodcucgfd to fhsudivycgeheekodod0djddvvff, dydhdidocjbcgtvctcyvcfdd

Answer 2

Answer:

Step-by-step explanation:

To solve this problem we can use partition method of Quick Sort but this would not preserve the original relative order of the nodes in each of the two partitions.

Below is the algorithm to solve this problem :  

 

Initialize first and last nodes of below three linked lists as NULL.  

  Linked list of values smaller than x.

  Linked list of values equal to x.

  Linked list of values greater than x.

Now iterate through the original linked list. If a node’s value is less than x then append it at the end of the smaller list. If the value is equal to x, then at the end of the equal list. And if a value is greater, then at the end of the greater list.

Now concatenate three lists.