Rearrange a linked list in to alternate first and last element
Given a linked list. arrange the linked list in manner of alternate first and last element.
Examples:
Input : 1->2->3->4->5->6->7->8 Output :1->8->2->7->3->6->4->5 Input :10->11->15->13 Output :10->13->11->15
We have discussed three different solution in Rearrange a given linked list in-place.
In this post a different Deque based solution is discussed.
Method:
- Create an empty deque
- Insert all element from the linked list to the deque
- Insert the element back to the linked list from deque in alternate fashion i.e first then last and so on
Implementation:
C++
// CPP program to rearrange a linked list in given manner #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to reverse the linked list */ void arrange( struct Node* head) { struct Node* temp = head; deque< int > d; // defining a deque // push all the elements of linked list in to deque while (temp != NULL) { d.push_back(temp->data); temp = temp->next; } // Alternatively push the first and last elements // from deque to back to the linked list and pop int i = 0; temp = head; while (!d.empty()) { if (i % 2 == 0) { temp->data = d.front(); d.pop_front(); } else { temp->data = d.back(); d.pop_back(); } i++; temp = temp->next; // increase temp } } /*UTILITY FUNCTIONS*/ /* Push a node to linked list. Note that this function changes the head */ void push( struct Node** head_ref, char new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // printing the linked list void printList( struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf ( "%d " , temp->data); temp = temp->next; } } /* Driver program to test above function*/ int main() { // Let us create linked list 1->2->3->4 struct Node* head = NULL; push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "Given linked list\t" ; printList(head); arrange(head); cout << "\nAfter rearrangement\t" ; printList(head); return 0; } |
Java
// Java program to rearrange a linked list in given manner import java.util.*; import java.lang.*; import java.io.*; class GFG { /* Link list node */ static class Node { int data; Node next; Node( int data) { this .data = data; next = null ; } } // printing the linked list static void printList(Node head) { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } } /* Function to reverse the linked list */ static void arrange(Node head) { // defining a deque Deque<Integer> deque = new ArrayDeque<>(); Node temp = head; // push all the elements of linked list in to deque while (temp != null ) { deque.addLast(temp.data); temp = temp.next; } temp = head; int i = 0 ; // Alternatively push the first and last elements // from deque to back to the linked list and pop while (!deque.isEmpty()) { if (i % 2 == 0 ) { temp.data = deque.removeFirst(); } else { temp.data = deque.removeLast(); } i++; temp = temp.next; } } // Driver code public static void main (String[] args) { // Let us create linked list 1->2->3->4->5 Node head = null ; head = new Node( 1 ); head.next = new Node( 2 ); head.next.next = new Node( 3 ); head.next.next.next = new Node( 4 ); head.next.next.next.next = new Node( 5 ); System.out.println( "Given linked list" ); printList(head); arrange(head); System.out.println( "\nAfter rearrangement" ); printList(head); } } // This code is contributed by nobody_cares. |
Python
# Python program to rearrange # a linked list in given manner # Link list node class Node: def __init__( self , data): self .data = data self . next = None # Function to reverse the linked list def arrange( head): temp = head # defining a deque d = [] # push all the elements of linked list in to deque while (temp ! = None ) : d.append(temp.data) temp = temp. next # Alternatively push the first and last elements # from deque to back to the linked list and pop i = 0 temp = head while ( len (d) > 0 ) : if (i % 2 = = 0 ) : temp.data = d[ 0 ] d.pop( 0 ) else : temp.data = d[ - 1 ] d.pop() i = i + 1 # increase temp temp = temp. next return head # UTILITY FUNCTIONS # Push a node to linked list. Note that this function # changes the head def push( head_ref, new_data): # allocate node new_node = Node( 0 ) # put in the data new_node.data = new_data # link the old list of the new node new_node. next = (head_ref) # move the head to point to the new node (head_ref) = new_node return head_ref # printing the linked list def printList( head): temp = head while (temp ! = None ) : print ( temp.data,end = " " ) temp = temp. next # Driver program to test above function # Let us create linked list 1.2.3.4 head = None head = push(head, 5 ) head = push(head, 4 ) head = push(head, 3 ) head = push(head, 2 ) head = push(head, 1 ) print ( "Given linked list\t" ) printList(head) head = arrange(head) print ( "\nAfter rearrangement\t" ) printList(head) # This code is contributed by Arnab Kundu |
C#
using System; using System.Collections.Generic; using System.Collections; using System.Linq; // C# program to rearrange a linked list in given manner /* Link list node */ class Node { public int data; public Node next; public Node( int val){ data = val; next = null ; } } class HelloWorld { /* Function to reverse the linked list */ public static void arrange(Node head) { Node temp = head; List< int > d = new List< int > (); // defining a deque // push all the elements of linked list in to deque while (temp != null ) { d.Add(temp.data); temp = temp.next; } // Alternatively push the first and last elements // from deque to back to the linked list and pop int i = 0; temp = head; while (d.Count > 0) { if (i % 2 == 0) { temp.data = d.First(); d.RemoveAt(0); } else { temp.data = d.Last(); d.RemoveAt(d.Count - 1); } i++; temp = temp.next; // increase temp } } /*UTILITY FUNCTIONS*/ /* Push a node to linked list. Note that this function changes the head */ public static Node push(Node head, int new_data) { /* allocate node */ Node new_node = new Node(new_data); /* link the old list of the new node */ new_node.next = head; /* move the head to point to the new node */ head = new_node; return head; } // printing the linked list public static void printList(Node head) { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } } static void Main() { // Let us create linked list 1->2->3->4 Node head = null ; head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); Console.Write( "Given linked list " ); printList(head); arrange(head); Console.Write( "\nAfter rearrangement " ); printList(head); } } // The code is contributed by Nidhi goel. |
Javascript
<script> // Javascript program to rearrange a linked list in given manner /* Link list node */ class Node { constructor() { this .data = 0; this .next = null ; } }; /* Function to reverse the linked list */ function arrange( head) { var temp = head; var d = []; // defining a deque // push all the elements of linked list in to deque while (temp != null ) { d.push(temp.data); temp = temp.next; } // Alternatively push the first and last elements // from deque to back to the linked list and pop var i = 0; temp = head; while (d.length!=0) { if (i % 2 == 0) { temp.data = d[0]; d.shift(); } else { temp.data = d[d.length-1]; d.pop(); } i++; temp = temp.next; // increase temp } } /*UTILITY FUNCTIONS*/ /* Push a node to linked list. Note that this function changes the head */ function push(head_ref, new_data) { /* allocate node */ var new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list of the new node */ new_node.next = (head_ref); /* move the head to point to the new node */ (head_ref) = new_node; return head_ref; } // printing the linked list function printList(head) { var temp = head; while (temp != null ) { document.write(temp.data+ " " ); temp = temp.next; } } /* Driver program to test above function*/ // Let us create linked list 1.2.3.4 var head = null ; head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); document.write( "Given linked list " ); printList(head); arrange(head); document.write( "<br>After rearrangement " ); printList(head); </script> |
Output
Given linked list 1 2 3 4 5 After rearrangement 1 5 2 4 3
Time Complexity : O(nlogn)
Auxiliary space: O(n) because using deque
Contact Us