Problem Description:
Given a singly linked list: A0→A1→→An-1→An,reorder it to: A0→An→A1→An-1→A2→An-2→
Given 1->2->3->4->5 its reorder is 1->5->2->4->3.
It is recommended do this in-place without altering the nodes’ values.
Input:
In this problem, methodtakes one argument: Address of the head of the linked list. The function should not read any input from stdin/console.
The node structure has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.
Output:
Reorder it as explained above.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
/* Following is the Linked list node structure */ /*struct node { int data; struct node* next; };*/ void reorderList(struct node* head) { // Your code here node *nodes[210]; int idx=0,last; node *tmp=head,*t; while(tmp) { idx+=1; nodes[idx]=tmp; tmp=tmp->next; } last=idx; for(int i=1;i<=idx/2;i++) { nodes[last-i]->next=NULL; tmp=nodes[last-i+1]; t=nodes[i]->next; nodes[i]->next=tmp; tmp->next=t; } } |