Reorder list in to alternate nodes like first lowest and first highest.

Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

The C++ 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++

/*
* File     : Re-order_list.cpp
*/

#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 ->