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 ordervoid 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 codeint 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 orderdef 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 codeclass 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.nextdef array_to_list(arr): ll = LinkedList() for item in arr: ll.insert(item) return ll.headif __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 orderfunction 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 codefunction 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.xclass Node: def __init__(self, data): self.data = data self.next = Nonedef 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 slowdef 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_middef 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.nextdef 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 arraylist.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.
Share your thoughts in the comments
