Print a singly linked list in spiral order - Coding

Given a Linked list, the task is to print a singly linked list in a spiral fashion, starting from the mid and rotating clockwise. If the linked list has even nodes, then you have to choose the left mid.

Examples:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> X
Output: 3 -> 4 -> 2 -> 5 -> 1 -> 6 -> X
Explanation:

Traversing linked list in spiral fashion

Input: 1 -> 2 -> 3 -> X
Output: 2 -> 3 -> 1 -> X

Naive Approach: There could be many approaches to solve this problem, one of the simplest approaches is here:

Storing the linked list data into ArrayList, and traversing the ArrayList by their indexes in spiral fashion.

Follow the given steps to solve the problem:

Create an ArrayList.
Traverse the linked list and insert the data in ArrayList.
Traverse it in a spiral fashion with two pointers, one from mid to left and the second from mid to end, one by one.

Following is the implementation of the above approach:

C++

#include <iostream>
#include <vector>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
    Node(int data) : data(data), next(nullptr) {}
};
 
// Function to print the linked list in spiral order
void printInSpiralForm(Node* head) {
    vector<int> list;
    Node* t = head;
 
    // Traversing the linked list and adding data to the vector
    while (t != nullptr) {
        list.push_back(t->data);
        t = t->next;
    }
 
    int n = list.size(), mid = (list.size() - 1) / 2;
    int left = mid, right = mid + 1;
 
    // Keep two pointers, one at mid, and the other at next to mid
    while (left >= 0 || right < n) {
        if (left >= 0)
            cout << list[left] << " -> ";
        if (right < n)
            cout << list[right] << " -> ";
        left--;
        right++;
    }
    cout << "X" << endl;
}
 
// Driver code
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* root = nullptr;
 
    // Create linked list from array
    for (int i = 0; i < n; i++) {
        Node* temp = new Node(arr[i]);
        if (root == nullptr)
            root = temp;
        else {
            Node* ptr = root;
            while (ptr->next != nullptr)
                ptr = ptr->next;
            ptr->next = temp;
        }
    }
 
    // Call the function to print in spiral form
    printInSpiralForm(root);
 
    // Clean up memory (free nodes)
    while (root != nullptr) {
        Node* temp = root;
        root = root->next;
        delete temp;
    }
 
    return 0;
}

Java

// Java code for the above approach:
import java.util.*;
public class Main {
    static class Node {
        int data;
        Node next;
    };
 
    // Function to print the linked list
    // in spiral order
    public static void printInSpiralForm(Node head)
    {
        ArrayList<Integer> list = new ArrayList<>();
        Node t = head;
 
        // Traversing the linked list and adding
        // data to arraylist
        while (t != null) {
            list.add(t.data);
            t = t.next;
        }
 
        int n = list.size(), mid = (list.size() - 1) / 2;
        int left = mid, right = mid + 1;
 
        // Keep two pointers one at mid,
        // and 2nd at next to mid.
        while (left >= 0 || right < n) {
            if (left >= 0)
                System.out.print(list.get(left) + " -> ");
            if (right < n)
                System.out.print(list.get(right) + " -> ");
            left--;
            right++;
        }
        System.out.println("X");
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 4, 5, 6 };
        int n = arr.length;
        Node root = arrayToList(arr, n);
 
        printInSpiralForm(root);
    }
 
    // Driver code starts
    static Node insert(Node root, int item)
    {
        Node temp = new Node();
        Node ptr;
        temp.data = item;
        temp.next = null;
 
        if (root == null)
            root = temp;
        else {
            ptr = root;
            while (ptr.next != null)
                ptr = ptr.next;
            ptr.next = temp;
        }
        return root;
    }
 
    // Driver code
    static void display(Node root)
    {
        while (root != null) {
            System.out.print(root.data + " ");
            root = root.next;
        }
    }
 
    // Driver code
    static Node arrayToList(int arr[], int n)
    {
        Node root = null;
        for (int i = 0; i < n; i++)
            root = insert(root, arr[i]);
        return root;
    }
}

Python3

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Function to print the linked list in spiral order
def print_in_spiral_form(head):
    lst = []
    t = head
 
    # Traversing the linked list and adding data to a list
    while t:
        lst.append(t.data)
        t = t.next
 
    n = len(lst)
    mid = (n - 1) // 2
    left = mid
    right = mid + 1
 
    # Keep two pointers, one at mid and the second at next to mid
    while left >= 0 or right < n:
        if left >= 0:
            print(lst[left], '->', end=' ')
        if right < n:
            print(lst[right], '->', end=' ')
        left -= 1
        right += 1
 
    print("X")
 
# Driver code
class LinkedList:
    def __init__(self):
        self.head = None
 
    def insert(self, item):
        temp = Node(item)
 
        if self.head is None:
            self.head = temp
        else:
            ptr = self.head
            while ptr.next:
                ptr = ptr.next
            ptr.next = temp
 
    def display(self):
        root = self.head
        while root:
            print(root.data, end=' ')
            root = root.next
 
def array_to_list(arr):
    ll = LinkedList()
    for item in arr:
        ll.insert(item)
    return ll.head
 
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6]
    root = array_to_list(arr)
 
    print_in_spiral_form(root)
#This code is Contributed by chinmaya121221

C#

// C# code for the above approach:
 
using System;
using System.Collections.Generic;
 
class Node
{
    public int Data;
    public Node Next;
 
    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}
 
class Program
{
    // Function to print the linked list in spiral order
    static void PrintInSpiralForm(Node head)
    {
        List<int> list = new List<int>();
        Node t = head;
 
        // Traversing the linked list and adding data to the list
        while (t != null)
        {
            list.Add(t.Data);
            t = t.Next;
        }
 
        int n = list.Count;
        int mid = (list.Count - 1) / 2;
        int left = mid;
        int right = mid + 1;
 
        // Keep two pointers, one at mid, and the other at next to mid
        while (left >= 0 || right < n)
        {
            if (left >= 0)
                Console.Write(list[left] + " -> ");
            if (right < n)
                Console.Write(list[right] + " -> ");
            left--;
            right++;
        }
        Console.WriteLine("X");
    }
 
    static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5, 6 };
        int n = arr.Length;
        Node root = null;
 
        // Create linked list from array
        for (int i = 0; i < n; i++)
        {
            Node newNode = new Node(arr[i]);
            if (root == null)
            {
                root = newNode;
            }
            else
            {
                Node ptr = root;
                while (ptr.Next != null)
                {
                    ptr = ptr.Next;
                }
                ptr.Next = newNode;
            }
        }
 
        // Call the function to print in spiral form
        PrintInSpiralForm(root);
 
        // Clean up memory (free nodes)
        while (root != null)
        {
            Node nextNode = root.Next;
            root.Next = null; // Release the node
            root = nextNode;
        }
    }
}

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
 
// Function to print the linked list in spiral order
function printInSpiralForm(head) {
    const list = [];
    let t = head;
 
    // Traversing the linked list and adding data to the array
    while (t !== null) {
        list.push(t.data);
        t = t.next;
    }
 
    const n = list.length;
    const mid = Math.floor((list.length - 1) / 2);
    let left = mid;
    let right = mid + 1;
 
    // Keep two pointers, one at mid, and the other at next to mid
    while (left >= 0 || right < n) {
        if (left >= 0) {
            console.log(list[left] + ' -> ');
        }
        if (right < n) {
            console.log(list[right] + ' -> ');
        }
        left--;
        right++;
    }
    console.log('X');
}
 
// Driver code
function main() {
    const arr = [1, 2, 3, 4, 5, 6];
    const n = arr.length;
    let root = null;
 
    // Create linked list from array
    for (let i = 0; i < n; i++) {
        const temp = new Node(arr[i]);
        if (root === null) {
            root = temp;
        } else {
            let ptr = root;
            while (ptr.next !== null) {
                ptr = ptr.next;
            }
            ptr.next = temp;
        }
    }
 
    // Call the function to print in spiral form
    printInSpiralForm(root);
 
    // Clean up memory (free nodes)
    while (root !== null) {
        const temp = root;
        root = root.next;
        // Delete temp; (Garbage collection will handle this in JavaScript)
    }
}
 
main();

Output

3 -> 4 -> 2 -> 5 -> 1 -> 6 -> X

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient Approach: To solve the problem follow the below idea:

Find mid. Reverse the linked list from start to mid. So that we can traverse it backwards also from mid to start, and traversing forwards from mid to end.

Follow the steps to solve the problem:

Find the mid of the list from where the spiral would start.
Reverse the list from the start to mid, so that we can traverse backwards from mid to left.
Lastly, traverse the list with two pointers from (mid to left) along with (mid+1 to right) one by one.

Following is the implementation of the above approach:

C++

#include <iostream>
using namespace std;
 
class Node {
public:
    int data;
    Node* next = nullptr;
    Node(int data) : data(data) {}
};
 
Node* head = nullptr;
Node* tail = nullptr;
 
Node* getMiddleOfList(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
 
Node* reverseListTillMid(Node* mid) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;
    Node* nextToMid = mid->next;
    while (current != nextToMid) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
    return nextToMid;
}
 
void print(Node* head, Node* secondhead) {
    Node* itr1 = head;
    Node* itr2 = secondhead;
    while (itr1 != nullptr && itr2 != nullptr) {
        cout << itr1->data << " -> ";
        cout << itr2->data << " -> ";
        itr1 = itr1->next;
        itr2 = itr2->next;
    }
    for (; itr1 != nullptr; itr1 = itr1->next)
        cout << itr1->data << " -> ";
    cout << "X" << endl;
}
 
void createList(int data[], int size) {
    for (int i = 0; i < size; i++) {
        if (head == nullptr) {
            head = new Node(data[i]);
            tail = head;
        }
        else {
            tail->next = new Node(data[i]);
            tail = tail->next;
        }
    }
}
 
void printInSpiralForm() {
    Node* mid = getMiddleOfList(head);
    Node* nextToMid = reverseListTillMid(mid);
    print(head, nextToMid);
}
 
int main() {
    int data[] = {1, 2, 3, 4, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    createList(data, size);
    printInSpiralForm();
 
    // Clean up memory (free nodes)
    Node* current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }
 
    return 0;
}

Java

// Java code for the above approach:
import java.util.*;
 
class Node {
    int data;
    Node next = null;
    Node(int data) { this.data = data; }
}
public class Solution {
    static Node head = null, tail = null;
    public static void main(String[] args)
    {
        int[] data = new int[] { 1, 2, 3, 4, 5, 6 };
        createList(data);
        printInSpiralForm();
 
        head = null;
        tail = null;
    }
    static void printInSpiralForm()
    {
 
        // Function to print the list
        // in spiral form
        Node mid = getMiddleOfList(head);
 
        // Reversing the list from start to mid,
        // and storing the other half list
        // reference in nextToMid.
        Node nextToMid = reverseListTillMid(mid);
 
        print(head, nextToMid);
    }
    private static Node getMiddleOfList(Node head)
    {
 
        // Finding mid with slow and fast pointer
        Node slow = head, fast = head;
 
        // But we need the left middle in case
        // of order, so little modification
        // in the while condition
        while (fast.next != null
               && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
 
        return slow;
    }
    static Node reverseListTillMid(Node mid)
    {
        Node prev = null, current = head, next = null;
        Node nextToMid = mid.next;
 
        // Need to reverse the list
        // till we encounter mid
        while (current != nextToMid) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
 
        head = prev;
        return next;
    }
    static void print(Node head, Node secondhead)
    {
 
        // Printing list with
        // two pointers one by one
        Node itr1 = head, itr2 = secondhead;
        while (itr1 != null && itr2 != null) {
            System.out.print(itr1.data + " -> ");
            System.out.print(itr2.data + " -> ");
            itr1 = itr1.next;
            itr2 = itr2.next;
        }
        for (; itr1 != null; itr1 = itr1.next)
            System.out.print(itr1.data + " -> ");
        System.out.print("X\n");
    }
 
    // Driver code
    static void createList(int[] data)
    {
        for (var i : data) {
            if (head == null) {
                head = new Node(i);
                tail = head;
            }
            else {
                tail.next = new Node(i);
                tail = tail.next;
            }
        }
    }
}

Python

from __future__ import print_function  # For compatibility with Python 2.x
 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
def get_middle_of_list(head):
    slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow
 
def reverse_list_till_mid(mid):
    global head  # Declare head as a global variable
    prev = None
    current = head
    next_node = None
    next_to_mid = mid.next
    while current != next_to_mid:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    head = prev
    return next_to_mid
 
def print_linked_lists(head, second_head):
    itr1 = head
    itr2 = second_head
    while itr1 is not None and itr2 is not None:
        print(itr1.data, " -> ", end="")
        print(itr2.data, " -> ", end="")
        itr1 = itr1.next
        itr2 = itr2.next
    for itr in [itr1, itr2]:
        while itr is not None:
            print(itr.data, " -> ", end="")
            itr = itr.next
    print("X")
 
def create_list(data):
    global head, tail
    for i in range(len(data)):
        if head is None:
            head = Node(data[i])
            tail = head
        else:
            tail.next = Node(data[i])
            tail = tail.next
 
def print_in_spiral_form():
    mid = get_middle_of_list(head)
    next_to_mid = reverse_list_till_mid(mid)
    print_linked_lists(head, next_to_mid)
 
if __name__ == "__main__":
    head = None
    tail = None
    data = [1, 2, 3, 4, 5, 6]
    create_list(data)
    print_in_spiral_form()
 
    current = head
    while current is not None:
        temp = current
        current = current.next
        del temp

C#

using System;
 
class Node
{
    public int Data { get; set; }
    public Node Next { get; set; }
 
    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}
 
class LinkedList
{
    private Node Head { get; set; } // Points to the start of the linked list
    private Node Tail { get; set; } // Points to the end of the linked list
 
    // Get the head of the linked list
    public Node GetHead()
    {
        return Head;
    }
 
    // Find the middle node of the linked list using slow and fast pointers
    public Node GetMiddleOfList(Node head)
    {
        Node slow = head;
        Node fast = head;
        while (fast?.Next != null && fast.Next.Next != null)
        {
            slow = slow.Next;
            fast = fast.Next.Next;
        }
        return slow;
    }
 
    // Reverse the linked list from the head to the middle node
    public Node ReverseListTillMid(Node mid)
    {
        Node prev = null;
        Node current = Head;
        Node next = null;
        Node nextToMid = mid.Next;
        while (current != nextToMid)
        {
            next = current.Next;
            current.Next = prev;
            prev = current;
            current = next;
        }
        Head = prev;
        return nextToMid;
    }
 
    // Print two linked lists in a spiral form
    public void Print(Node head, Node secondHead)
    {
        Node itr1 = head;
        Node itr2 = secondHead;
        while (itr1 != null && itr2 != null)
        {
            Console.Write(itr1.Data + " -> ");
            Console.Write(itr2.Data + " -> ");
            itr1 = itr1.Next;
            itr2 = itr2.Next;
        }
        for (; itr1 != null; itr1 = itr1.Next)
        {
            Console.Write(itr1.Data + " -> ");
        }
        Console.WriteLine("X");
    }
 
    // Create a linked list from an array of integers
    public void CreateList(int[] data)
    {
        for (int i = 0; i < data.Length; i++)
        {
            if (Head == null)
            {
                Head = new Node(data[i]);
                Tail = Head;
            }
            else
            {
                Tail.Next = new Node(data[i]);
                Tail = Tail.Next;
            }
        }
    }
 
    // Print the linked list in a spiral form
    public void PrintInSpiralForm()
    {
        Node mid = GetMiddleOfList(Head); // Find the middle of the list
        Node nextToMid = ReverseListTillMid(mid); // Reverse the list till the middle
        Print(Head, nextToMid); // Print in a spiral form
    }
}
 
class Program
{
    static void Main()
    {
        int[] data = { 1, 2, 3, 4, 5, 6 };
        LinkedList list = new LinkedList();
        list.CreateList(data); // Create a linked list from the array
        Node head = list.GetHead(); // Get the head node
        list.PrintInSpiralForm(); // Print the linked list in spiral form
 
        // Clean up memory (free nodes)
        Node current = head;
        while (current != null)
        {
            current = current.Next; // No need for a temporary variable
        }
    }
}

Javascript

class Node {
    constructor(data) {
        this.data = data; // Node's data
        this.next = null; // Pointer to the next node
    }
}
 
class LinkedList {
    constructor() {
        this.head = null; // Points to the start of the linked list
        this.tail = null; // Points to the end of the linked list
    }
 
    // Create a linked list from an array of data elements
    createList(data) {
        for (let i = 0; i < data.length; i++) {
            if (!this.head) {
                this.head = new Node(data[i]); // Create the first node if head is null
                this.tail = this.head; // Set the tail as the head initially
            } else {
                this.tail.next = new Node(data[i]); // Add a new node to the end of the list
                this.tail = this.tail.next; // Update the tail to the new node
            }
        }
    }
 
    // Find the middle node of the linked list using slow and fast pointers
    getMiddleOfList(head) {
        let slow = head; // Slow pointer starts at the head
        let fast = head; // Fast pointer starts at the head
        while (fast?.next && fast.next.next) {
            slow = slow.next; // Move slow pointer by one node
            fast = fast.next.next; // Move fast pointer by two nodes
        }
        return slow; // Return the middle node using the slow pointer
    }
 
    // Reverse the linked list from the head to the middle node
    reverseListTillMid(mid) {
        let prev = null;
        let current = this.head;
        let next = null;
        let nextToMid = mid.next; // Next to the middle node
        while (current !== nextToMid) {
            next = current.next; // Store the next node
            current.next = prev; // Reverse the pointer
            prev = current; // Move to the next node
            current = next; // Move to the next node
        }
        this.head = prev; // Update the head of the list
        return nextToMid; // Return the node next to the middle
    }
 
    // Print nodes of two linked lists in a spiral form
    print(head, secondHead) {
        let itr1 = head;
        let itr2 = secondHead;
        while (itr1 && itr2) {
            console.log(itr1.data + " -> " + itr2.data + " -> "); // Print elements from both lists
            itr1 = itr1.next; // Move to the next node in the first list
            itr2 = itr2.next; // Move to the next node in the second list
        }
        for (; itr1; itr1 = itr1.next) {
            console.log(itr1.data + " -> "); // Print remaining nodes of the first list
        }
        console.log("X"); // End of the list
    }
 
    // Print the linked list in a spiral form
    printInSpiralForm() {
        const mid = this.getMiddleOfList(this.head); // Find the middle of the list
        const nextToMid = this.reverseListTillMid(mid); // Reverse the list till the middle
        this.print(this.head, nextToMid); // Print in a spiral form
    }
}
 
const data = [1, 2, 3, 4, 5, 6];
const list = new LinkedList();
list.createList(data); // Create a linked list from the array
list.printInSpiralForm(); // Print the linked list in spiral form

Output

3 -> 4 -> 2 -> 5 -> 1 -> 6 -> X

Time complexity: O(N)
Auxiliary Space: O(1), since no extra space is used.

Reffered: https://www.geeksforgeeks.org

DSA

Related
Find the Root of a Tree
Accessing characters by index in a String
Minimum swaps required in the String such that S[i] != S[n-i+1]
Count the unique type of nodes present in Binary tree
Link List sum and Prime Insertion

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11