Reorder List

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

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

Example:

Input:  1->2->3->4->NULL
Output: 1->4->2->3->NULL

Approach

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReorderList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        reorderList(head);
        linkedListTraversal(head);
    }

    static void reorderList(ListNode head) {
        Stack<ListNode> st = new Stack<ListNode>();
        Queue<ListNode> q = new LinkedList<ListNode>();

        if (head == null || head.next == null)
            return;
        ListNode temp = head.next;
        while (temp != null) {
            st.add(temp);
            q.add(temp);
            temp = temp.next;
        }
        temp = head;
        ListNode temp1 = null;
        while (true) {
            if (st.peek() == q.peek()) {
                temp.next = q.peek();
                temp.next.next = null;
                break;
            }
            temp.next = st.pop();
            temp = temp.next;
            temp.next = q.poll();
            temp1 = temp.next;
            temp = temp.next;
            if (temp1 == st.peek()) {
                temp.next = null;
                break;
            }
        }
    }

    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;
    

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//Struture of  node
struct Node
{ 
   int data;
   Node *next;
   Node(int data)
    {
        this->data=data;
        this->next=NULL;
    }
};

void reorderList(Node* head) 
{
       stack<Node*> st;
       queue<Node*> q;
       
        if(head==NULL||head->next==NULL)
              return ;
         Node *temp=head->next;
       while(temp!=NULL)
       {
           st.push(temp);
           q.push(temp);
           temp=temp->next;
       }
       temp=head;
       Node *temp1=NULL;
       while(true)
       {
          if(st.top()==q.front())
          {
              temp->next=q.front();
              temp->next->next=NULL;
              break;
          }
          temp->next=st.top();
           st.pop();
           temp=temp->next;
          temp->next=q.front();
          q.pop();
          temp1=temp->next;
           temp=temp->next;
           if(temp1==st.top())
           {
               temp->next=NULL;
               break;
           }
       }
}

//function to traverse a linked 
//list
void linkedListTraversal(Node *head)
{
    Node *temp=head;
    //iterate till we reach end of the linked 
    //list
    while(temp!=NULL)
     {
         //print the current
         //node data
         cout<<temp->data<<" ";
         //move to next node
         temp=temp->next;
     }
}

int main()
{
  Node *head=new Node(1);
  head->next=new Node(2);
  head->next->next=new Node(3);
  head->next->next->next=new Node(4);

  reorderList(head);
  linkedListTraversal(head);
  return 0;
}