Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
Example 1: Given 1->2->3->4, reorder it to 1->4->2->3.
The algorithm will works as shown below:
Step 1: Find the middle of the list.
Step 2: Reverse the second half of the list.
Step 3: Merge them.
Solution in C++
#include<iostream> #include<vector> using namespace std; struct Node { public: int data; Node *next; Node(int x) { data = x; next = NULL; } }; void reorder_list(Node *head) { Node *head_1; // head_1 will hold starting of the first half of the list Node *head_2; // head_2 will hold the starting of the second half of the list // below 2 pointers are used to reverse the list Node *preNode = NULL; Node *curNode = NULL; head_1 = head; head_2 = head->next; // find the starting point of the second half while(head_2 && head_2->next) { head_1 = head_1->next; head_2 = (head_2->next)->next; } // the head_2 will hold the head of the second half head_2 =head_1->next; head_1->next =NULL; //reverse the second half while(head_2) { curNode = head_2->next; head_2->next = preNode; preNode= head_2; head_2 = curNode; } // merge the first half and the reversed second half head_2 = preNode; head_1 = head; while(head_2) { curNode = head_1->next; head_1 = head_1->next = head_2; head_2 = curNode; } return; } void print_list(Node *head) { Node *ptr = head; while(ptr) { cout<< ptr->data << " -> "; ptr = ptr->next; } cout<<endl; } int main() { Node *start = new Node(1); start -> next = new Node(2); start -> next -> next = new Node(3); start -> next -> next -> next = new Node(4); start -> next -> next -> next -> next = new Node(5); start -> next -> next -> next -> next -> next = new Node(6); cout<<"Original List :"<<endl; print_list(start); reorder_list(start); cout<<"Re-Ordered List :"<<endl; print_list(start); return 0; }
Output:
Original List : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Re-Ordered List : 1 -> 6 -> 2 -> 5 -> 3 -> 4 ->