Rearrange a Linked List in Zig Zag Fashion

Introduction

A linked list is nothing but a linear collection of elements of a similar type in computer programming. Each node points towards the upcoming node in a linked list, thus creating a link or a chain. In the most basic form, a linked list consists of multiple nodes, and each node contains some data and a reference or a link to the next node present in the sequence. 

In this blog, we will discuss all the possible ways to rearrange a linked list in a zig-zag fashion. To satisfy the zig-zag condition, the Linked List should be arranged such that x < y > z where x, y, and z are consecutive nodes of the Linked List.

Input: 1->2->3->4
Output: 1->3->2->4
Explanation: One and three will come before two and four.


Input: 11->15->20->5->10
Output: 11->20->5->15-10
Explanation: 20 is greater than both 11 and 5. Similarly, 15 is greater than both 5 and 10.

Recommended Topic, Floyds Algorithm

Example

In the given solutions we will transverse through all the elements present in the list. If the current and the next element don’t satisfy the given condition we will raise a flag and swap the values. The auxiliary space and the time complexity remain O(n) for both solutions.

Auxiliary Space: It is the number of extra space data structures required for storing the values.

Time Complexity: Time Complexity can be defined as the time required by a computer to perform an algorithm given the worst-case scenario for that algorithm.

First Approach

In this approach, we will use a single scan similar to a bubble sort to maintain a flag. If the current two nodes are in the above-mentioned order, we don’t swap them. Otherwise, we swap them.

class ZigZag1 {
static class Node {
int data;
Node next;
}
static Node head = null;
static int temp = 0;
static void zigZagList(Node head)
{
boolean flag = true;
Node current = head;
while (current != null && current.next != null) {
if (flag == true)
{
if (current.data > current.next.data) {
temp = current.data;
current.data = current.next.data;
current.next.data = temp;
}
}
else
{
if (current.data < current.next.data) {
temp = current.data;
current.data = current.next.data;
current.next.data = temp;
}
}


current = current.next;
flag = !(flag);
}
}
static void push(int new_data)
{
Node new_Node = new Node();
new_Node.data = new_data;
new_Node.next = (head);
(head) = new_Node;
}
static void printList(Node Node)
{
while (Node != null) {
System.out.print(Node.data + "->");
Node = Node.next;
}
System.out.println("NULL\n");
}


public static void main(String[] args)
{
push(10);
push(5);
push(20);
push(15);
push(11);
System.out.println("\n\nGiven linked list: ");
printList(head);
zigZagList(head);
System.out.println("\nZig Zag Linked list: ");
printList(head);
}
}

You can also try this code with Online Java Compiler

Run Code

The time complexity of this approach is O(n), where n is the number of elements present in the linked list. Since there are n elements in the list, the compiler will need to transverse through n elements, thus the complexity is O(n).

Second Approach

The second approach is quite similar to the first approach, and we will be traversing through the list only once. The idea of using a flag value also remains the same in this case. You can also use this approach, while both the approaches have the same time complexity, in some circumstances the interviewer might ask to implement another approach.

import java.io.*;
class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
public class ZigZag2{
private Node head;
public void printList()
{
Node t = head;
while (t != null) {
System.out.print(t.data + " ->");
t = t.next;
}
System.out.println();
}
public void swap(Node a, Node b)
{
if (a == null || b == null)
return;
int temp = a.data;
a.data = b.data;
b.data = temp;
}
public Node zigZag(Node node, int flag)
{
if (node == null || node.next == null) {
return node;
}
if (flag == 0) {
if (node.data > node.next.data) {
swap(node, node.next);
}
return zigZag(node.next, 1);
}
else {
if (node.data < node.next.data) {
swap(node, node.next);
}
return zigZag(node.next, 0);
}
}
public static void main(String[] args)
{
ZigZag2 obj = new ZigZag2();
obj.head = new Node(11);
obj.head.next = new Node(15);
obj.head.next.next = new Node(20);
obj.head.next.next.next = new Node(5);
obj.head.next.next.next.next = new Node(10);
System.out.println("\n\nGiven linked list: ");
obj.printList();
int flag = 0;
obj.zigZag(obj.head, flag);
System.out.println("\nZig Zag Linked list: ");
obj.printList();
}
}

You can also try this code with Online Java Compiler

Run Code

Same as in the above code the time complexity for this solution also remains O(n), where n is the number of elements present in the linked list. Since there are n elements in the list, the compiler will need to transverse through n elements, thus the complexity is O(n).