Microsoft Interview Question
Country: India
Start scanning the linked list , the point/link where you find ptr->data > ptr->next->data , stop scanning.
Now temp_start = ptr->next
Now reverse temp_start link list.
Assign as ptr->next = temp_start
ideone.com/LGFEm
void correctList(struct node *root)
{
struct node *cur,*prev,*mark1,*mark2,*p,*q,*r;
if(!root || !(root->next))
return;
cur=root;prev=NULL;
while(cur->next && cur->data<cur->next->data)
{
prev=cur;
cur=cur->next;
}
mark1=prev;
prev=mark1->next;
while(cur->next && cur->data>cur->next->data)
cur=cur->next;
mark2=cur->next;
p=r=NULL;q=mark1->next;
while(q!=mark2)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
mark1->next=p;
prev->next=mark2;
}
Here is the perfectly running code. I have used reverse function to reverse the sublist.
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *next;
};
void push(struct node **headref, int dat) {
struct node *newnode = malloc(sizeof(struct node));
newnode->data = dat;
newnode->next = *headref;
*headref = newnode;
}
void reverse(struct node **headref) {
struct node *first, *rest;
first = *headref;
if(first == NULL) {
return;
}
rest = first->next;
if(rest == NULL) {
return;
}
reverse(&rest);
first->next->next = first;
first->next = NULL;
*headref = rest;
}
void correct_list(struct node **headref) {
struct node *current = *headref;
struct node *mark1, *mark2, *root;
while(current->next != NULL && current->data < current->next->data) {
mark1 = current;
current = current->next;
}
current = mark1->next;
while(current->next != NULL && current->data > current->next->data) {
current = current->next;
}
mark2 = current->next;
current->next = NULL;
root = mark1->next;
reverse(&root);
mark1->next = root;
while(root->next != NULL) {
root = root->next;
}
root->next = mark2;
}
int main() {
struct node *root = NULL;
push(&root, 10);
push(&root, 9);
push(&root, 5);
push(&root, 6);
push(&root, 7);
push(&root, 8);
push(&root, 4);
push(&root, 3);
push(&root, 2);
push(&root, 1);
correct_list(&root);
while(root != NULL) {
printf("%d ",root->data);
root = root->next;
}
printf("\n");
system("pause");
return 0;
}
Please find the code below.. Please correct me if anything goes wrong. I hope it works for for all different inputs.
struct node* correctTheReversedSubListOfSortedList(struct node *root) {
struct node* ptr = root;
struct node* firstSegmentEnd = NULL; // This is the end of the first segment i.e. before the reversed list starts
while(ptr) {
if(ptr->next == NULL) break;
if(ptr->data <= ptr->next->data) {
firstSegmentEnd = ptr;
ptr = ptr->next;
} else {
// reverse the sub linked list
struct node* reverseHead = ptr; // Initially this is the start point where the reversed list start : After reversing done this will be the end of the reversed list
struct node* prev = NULL;
while(ptr && ptr->next && ptr->data > ptr->next->data) {
struct node* temp = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = temp;
}
struct node* lastSegmentStart = ptr->next; // last SegmentStart is the next pointer of where the reversed list ends
ptr->next = prev; // Now ptr contains the corrected reversed list start point
reverseHead->next = lastSegmentStart; //assign the lastSegmentPart to the end of the corrected reversed list
if(firstSegmentEnd) {
firstSegmentEnd->next = ptr; // assign the ptr to firstSegmentPart
} else {
// This case hits when the input list is totally in descending order i.e. entire list is reversed
root = ptr;
}
}
}
return root;
}
/// <summary>
/// 1--->2--->3--->4--->9--->8-->7--->6--->5--->10--->11--->NULL
/// </summary>
/// <param name="head"></param>
public static void correctList(Node<int> head)
{
if (head == null)
{
Console.WriteLine("Empty List");
return;
}
Node<int> current = head;
Node<int> first = null;
Node<int> last = null;
Node<int> mark1 = null;
while (current != null && current.NodeValue < current.NextNode.NodeValue)
{
mark1 = current;
current = current.NextNode;
}
first = current; //Pointer to node, LL Disorder starts
while (current != null && current.NodeValue > current.NextNode.NodeValue)
current = current.NextNode;
last = current.NextNode; //Pointer to node, LL Disorder Ends
current.NextNode = null; // Setting next of last node to null
Reverse(ref first);// reverse the sub linklist that dis order starts to disorder ends
mark1.NextNode = first; // join the intial linklist with reversed lkinked list
while (first.NextNode != null)
{
first = first.NextNode;
}
first.NextNode = last; // join the merged link list with sorted linklist
Console.WriteLine();
Console.WriteLine("Output");
PrintList(head);
Console.WriteLine();
}
public static void Reverse(ref Node<int> head)
{
Node<int> first;
Node<int> rest;
if (head == null) return;
first = head;
rest = first.NextNode;
if (rest == null) return;
Reverse(ref rest);
first.NextNode.NextNode = first;
first.NextNode = null;
head = rest;
}
public static void PrintList(Node<int> head)
{
while (head != null)
{
Console.Write(head.NodeValue);
head = head.NextNode;
if (head != null) Console.Write("->");
}
}
node *sublistloop(node *beg)
{
node *stop,*y,*prepre=NULL,*p1,*pre=NULL,*temp,*x,*st=beg;
int flag=0;
prepre=beg;
beg=beg->next;
pre=beg;
beg=beg->next;
if(beg==NULL)
return NULL;
while(beg!=NULL)
{
if(beg->data<pre->data&&flag==0)
{
p1=prepre;
flag=1;
x=pre;
}
else if(flag==1&&(beg->data>pre->data))
{
y=beg;
stop=pre;
break;
}
prepre=pre;
pre=beg;
beg=beg->next;
}
cout<<"x :"<<x->data<<"p1 :"<<p1->data<<"prepre :"<<prepre->data<<"y :"<<y->data<<"stop :"<<stop->data<<endl;
flag=0;
while(1)
{
if(x==stop)
flag=1;
temp=x->next;
x->next=y;
y=x;
x=temp;
if(flag==1)
break;
}
p1->next=y;
return st;
// 1->2->3->4->8->7->6->5->9->10
ListNode* correct(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* h = head, prev = NULL;
while (h->next && h->val < h->next->val {
prev = head;
h = h->next;
}
// start reversing till u reach 9 (in this eg)
// 1 -> 2->3->4 8 7 6 5 9 10
ListNode* first = h, p = NULL, fut = NULL;
while (h->next && h->val > h->next->val) {
fut = h->next;
h->next = p;
p = h;
h = fut;
}
first->next = h->next;
h->next = p;
if (prev) prev->next = h;
else head = h;
return head;
}
Simple Algorithm can do this
a) start from the begining of the list and travel till the point where your current node->info+1 =current node->next->info
the code for this is
- phani krishna Amazon November 16, 2012while(CurrentNode->info+1==CurentNode->next->info) { CurrentNode=CurrentNode->Next; } In this case you will reach node 4 , the point till your list from the begining is following an ascending order b) Now assign this node to some other node called StartNode StartNode=CurrentNode. c) Now from here traverse the list where you find the right node which is +1 ahead of your StratNode . In this case this is node 5. The code for this is while(StratNode->info+1 != CurrentNode->next->info) { CurrentNode=CurrentNode->Next; } Your EndNode will be 5 which is CurrentNode->next in this case EndNode=CurrentNode->next c) Now your StartNode=4 and your EndNode=5 for which we have to set up the link d) Now take a stack and push all items from StratNode to EndNode. e) Now pop every item and establish the link from StartNode and it looks like 4->5->6->7->8