Rearrange a linked list into alternate fashion first and the last element
Rearrange a linked list into alternate fashion first and the last element
This article will explain how to rearrange the linked list into alternate fashion first and the last element. Here, we have given a singly linked list, and we need to arrange the given linked list alternately, like the first element, then the last element, and so on.
Example: -
Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16
Output: 2 -> 16 -> 4 -> 14 -> 6 -> 12 -> 8 -> 10
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3
Method:
We can do this by using the following steps:
- Firstly, we will divide the given linked list into two parts.
- Then, we will reverse the second part of the linked list.
- After this, we will merge the first part and second part of the linked list in an alternate fashion.
Java program to rearrange a linked list into alternate fashion first and last element
import java.util.*;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public class RearrangeLinkedList
{
Node head, second;
/* Function to print linked list */
void traverse(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Function for reverse the linked list */
Node reverse(Node temp)
{
Node prev = null;
Node current = temp;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Function for find the middle node of the linked list
public static Node findMiddle(Node head)
{
Node prev = null;
Node slow = head, fast = head;
// find the middle pointer
while (fast != null && fast.next != null)
{
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
// for odd nodes, fix middle
if (fast != null && fast.next == null)
{
prev = slow;
slow = slow.next;
}
// make next of previous node null
prev.next = null;
// return middle node
return slow;
}
// Function for rearranging the linked list in an alternate fashion
public void rearrange(Node head)
{
if (head == null)
return;
Node middle = findMiddle(head);
second = reverse(middle);
head=merge(head, second);
}
// Function for merge the first and second halves of the linked list
public Node merge(Node first, Node second)
{
if (first == null) {
return second;
}
if (second == null) {
return first;
}
Node recursion = merge(first.next, second.next);
Node res = first;
first.next = second;
second.next = recursion;
return res;
}
// Driver Function
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the total no of elements in linked list: ");
int n = sc.nextInt();
System.out.println("Enter the elements of linked list: ");
int a1 = sc.nextInt();
RearrangeLinkedList ob = new RearrangeLinkedList();
Node head = new Node(a1);
Node tail = head;
for (int i = 1; i < n; i++)
{
int a = sc.nextInt();
tail.next = new Node(a);
tail = tail.next;
}
ob.rearrange(head);
System.out.print("Rearranged List:-");
ob.traverse(head);
}
}
Output:
Time Complexity: The time complexity of this method is O(n).