Last Updated: Mar 27, 2024

# Rearrange a Linked List in Zig Zag Fashion

## Introduction

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 int temp = 0;
{
boolean flag = true;
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;
}
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);
}
}

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{
public void printList()
{
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.printList();
int flag = 0;
obj.printList();
}
}

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).

#### What is a linked list?

In computer programming linked list is nothing but a linear collection of elements of a similar type. Each element points towards the next element 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.

#### What is time complexity in Data Structure?

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

#### What is Data Structure?

Data Structure is the method of arranging data or resources in a computer such that the system can run effectively and produce maximum efficiency.

#### What is Java?

Java is an object-oriented, class-based, high-level programming language. It is based on the concept of WORA (write once use anywhere) for developer ease.

The advantage of using a linked list over the traditional arrays is that it is much easier to insert or delete values from a linked list. Unlike the conventional arrays, there is no need for reallocation or reorganization.

## Conclusion

This blog covered all the necessary points about some of the possible ways to rearrange a linked list in a zig-zag manner. We further looked at an example to understand the implementation.

Do check out our blogs on object-oriented programming and data structures

Donâ€™t stop here. Check out Coding Ninjas for more unique courses and guided paths. Also, try Coding Ninjas Studio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems.

Topics covered
1.
Introduction
2.
Example
2.1.
First Approach
2.2.
Second Approach
3.