A linked list L0 -> L1 -> L2 -> ….. -> LN can be folded as L0 -> LN -> L1 -> LN – 1 -> L2 -> …..
Given a folded linked list, the task is to unfold and print the original linked list
Examples:
Input: 1 -> 6 -> 2 -> 5 -> 3 -> 4
Output: 1 2 3 4 5 6Input: 1 -> 5 -> 2 -> 4 -> 3
Output: 1 2 3 4 5
Approach: Make a recursive call and store the next node in temp pointer, first node will act as head node and the node which is stored in temp pointer will act as a tail of the list. On returning after reaching the base condition link the head and tail to previous head and tail respectively.
Base condition: If number of nodes is even then the second last node is head and the last node is tail and if the number of nodes is odd then last node will act as head as well as tail.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;// Node Classstruct Node{ int data; Node *next;};// Head of the listNode *head;// Tail of the listNode *tail;// Function to print the listvoid display(){ if (head == NULL) return; Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } cout << endl;}// Function to add node in the listvoid push(int data){ // Create new node Node* nn = new Node(); nn->data = data; nn->next = NULL; // Linking at first position if (head == NULL) { head = nn; } else { Node* temp = head; while (temp->next != NULL) { temp = temp->next; } // Linking at last in list temp->next = nn; }}// Function to unfold the given link listvoid unfold(Node* node){ if (node == NULL) return; // This condition will reach if // the number of nodes is odd // head and tail is same i->e-> last node if (node->next == NULL) { head = tail = node; return; } // This base condition will reach if // the number of nodes is even // mark head to the second last node // and tail to the last node else if (node->next->next == NULL) { head = node; tail = node->next; return; } // Storing next node in temp pointer // before making the recursive call Node* temp = node->next; // Recursive call unfold(node->next->next); // Connecting first node to head // and mark it as a new head node->next = head; head = node; // Connecting tail to second node (temp) // and mark it as a new tail tail->next = temp; tail = temp; tail->next = NULL;}// Driver codeint main(){ // Adding nodes to the list push(1); push(5); push(2); push(4); push(3); // Displaying the original nodes display(); // Calling unfold function unfold(head); // Displaying the list // after modification display();}// This code is contributed by pratham76 |
Java
// Java implementation of the approachpublic class GFG { // Node Class private class Node { int data; Node next; } // Head of the list private Node head; // Tail of the list private Node tail; // Function to print the list public void display() { if (head == null) return; Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } // Function to add node in the list public void push(int data) { // Create new node Node nn = new Node(); nn.data = data; nn.next = null; // Linking at first position if (head == null) { head = nn; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } // Linking at last in list temp.next = nn; } } // Function to unfold the given link list private void unfold(Node node) { if (node == null) return; // This condition will reach if // the number of nodes is odd // head and tail is same i.e. last node if (node.next == null) { head = tail = node; return; } // This base condition will reach if // the number of nodes is even // mark head to the second last node // and tail to the last node else if (node.next.next == null) { head = node; tail = node.next; return; } // Storing next node in temp pointer // before making the recursive call Node temp = node.next; // Recursive call unfold(node.next.next); // Connecting first node to head // and mark it as a new head node.next = head; head = node; // Connecting tail to second node (temp) // and mark it as a new tail tail.next = temp; tail = temp; tail.next = null; } // Driver code public static void main(String[] args) { GFG l = new GFG(); // Adding nodes to the list l.push(1); l.push(5); l.push(2); l.push(4); l.push(3); // Displaying the original nodes l.display(); // Calling unfold function l.unfold(l.head); // Displaying the list // after modification l.display(); }} |
Python3
# Python3 implementation of the approach# Node Classclass Node: def __init__(self, data): self.data = data self.next = None# Head of the listhead = None# Tail of the listtail = None# Function to print the listdef display(): if (head == None): return temp = head while (temp != None): print(temp.data, end = " ") temp = temp.next print()# Function to add node in the listdef push(data): global head, tail # Create new node nn = Node(data) # Linking at first position if (head == None): head = nn else: temp = head while (temp.next != None): temp = temp.next # Linking at last in list temp.next = nn# Function to unfold the given link listdef unfold(node): global head, tail if (node == None): return # This condition will reach if # the number of nodes is odd # head and tail is same i.e. last node if (node.next == None): head = tail = node return # This base condition will reach if # the number of nodes is even # mark head to the second last node # and tail to the last node elif (node.next.next == None): head = node tail = node.next return # Storing next node in temp pointer # before making the recursive call temp = node.next # Recursive call unfold(node.next.next) # Connecting first node to head # and mark it as a new head node.next = head head = node # Connecting tail to second node (temp) # and mark it as a new tail tail.next = temp tail = temp tail.next = None# Driver codeif __name__=='__main__': # Adding nodes to the list push(1) push(5) push(2) push(4) push(3) # Displaying the original nodes display() # Calling unfold function unfold(head) # Displaying the list # after modification display()# This code is contributed by rutvik_56 |
C#
// C# implementation of the approachusing System;public class GFG { // Node Class private class Node { public int data; public Node next; } // Head of the list private Node head; // Tail of the list private Node tail; // Function to print the list public void display() { if (head == null) return; Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } // Function to add node in the list public void push(int data) { // Create new node Node nn = new Node(); nn.data = data; nn.next = null; // Linking at first position if (head == null) { head = nn; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } // Linking at last in list temp.next = nn; } } // Function to unfold the given link list private void unfold(Node node) { if (node == null) return; // This condition will reach if // the number of nodes is odd // head and tail is same i.e. last node if (node.next == null) { head = tail = node; return; } // This base condition will reach if // the number of nodes is even // mark head to the second last node // and tail to the last node else if (node.next.next == null) { head = node; tail = node.next; return; } // Storing next node in temp pointer // before making the recursive call Node temp = node.next; // Recursive call unfold(node.next.next); // Connecting first node to head // and mark it as a new head node.next = head; head = node; // Connecting tail to second node (temp) // and mark it as a new tail tail.next = temp; tail = temp; tail.next = null; } // Driver code public static void Main() { GFG l = new GFG(); // Adding nodes to the list l.push(1); l.push(5); l.push(2); l.push(4); l.push(3); // Displaying the original nodes l.display(); // Calling unfold function l.unfold(l.head); // Displaying the list // after modification l.display(); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript implementation of the approach// Represents node of the linked listclass Node { constructor() { this.data = 0; this.next = null; } } // Head of the listvar head = null;// Tail of the listvar tail = null;// Function to print the listfunction display() { if (head == null) return; var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write("</br>"); }// Function to add node in the listfunction push( data){ // Create new node var nn = new Node(); nn.data = data; nn.next = null; // Linking at first position if (head == null) { head = nn; } else { var temp = head; while (temp.next != null) { temp = temp.next; } // Linking at last in list temp.next = nn; }}// Function to unfold the given link listfunction unfold( node){ if (node == null) return; // This condition will reach if // the number of nodes is odd // head and tail is same i.e. last node if (node.next == null) { head = tail = node; return; } // This base condition will reach if // the number of nodes is even // mark head to the second last node // and tail to the last node else if (node.next.next == null) { head = node; tail = node.next; return; } // Storing next node in temp pointer // before making the recursive call var temp = node.next; // Recursive call unfold(node.next.next); // Connecting first node to head // and mark it as a new head node.next = head; head = node; // Connecting tail to second node (temp) // and mark it as a new tail tail.next = temp; tail = temp; tail.next = null;}// Driver Code// Adding nodes to the listpush(1);push(5);push(2);push(4);push(3);// Displaying the original nodesdisplay();// Calling unfold functionunfold(head);// Displaying the list// after modificationdisplay();// This code is contributed by jana_sayantan.</script> |
Output
1 5 2 4 3 1 2 3 4 5
Time Complexity: O(N), where N is the total number of nodes in the linked list.
Auxiliary Space: O(N)
Iterative Approach:-
Approach: First we have to segregate the linked list on the basis of even-odd index. Then we reverse the odd part of segregated list and joined with the first list. This approach does not use recursive space.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;class ListNode {public: int val = 0; ListNode* next = nullptr; ListNode(int val) { this->val = val; }};ListNode* reverse(ListNode* head){ ListNode *prev = NULL, *temp = head, *copy = NULL; while (temp != NULL) { copy = temp->next; temp->next = prev; prev = temp; temp = copy; } return prev;}void unfold(ListNode* head){ // for segregating the original linked list into two // linked list on the basis of even and odd int i = 0; // For storing the previous node // and head node for each linked list ListNode *prev1 = NULL, *prev2 = NULL, *h1 = head, *h2 = head; while (head != NULL) { if (i % 2 == 0) { if (prev1 == NULL) { h1 = head; prev1 = head; } else { prev1->next = head; prev1 = head; } } else { if (prev2 == NULL) { h2 = head; prev2 = head; } else { prev2->next = head; prev2 = head; } } i++; head = head->next; } prev2->next = NULL; ListNode* rev = reverse(h2); // reverse the second linked list prev1->next = rev; // join the first ll with second one}void printList(ListNode* node){ ListNode* curr = node; while (curr != nullptr) { cout << curr->val << " "; curr = curr->next; } cout << endl;}int main(){ int n; ListNode* dummy = new ListNode(-1); ListNode* prev = dummy; n=5;int i=0; int arr[]={1, 5, 2, 4, 3}; //Elements in the linkedlist while (i < n) { prev->next = new ListNode(arr[i]); prev = prev->next; i++; } ListNode* head = dummy->next; printList(head); unfold(head); printList(head); return 0;}// This code is contributed by Ankit |
Java
// Java implementation of the approachclass GFG { static class ListNode { int val = 0; ListNode next = null; ListNode(int val) { this.val = val; } } static ListNode reverse(ListNode head) { ListNode prev = null, temp = head, copy = null; while (temp != null) { copy = temp.next; temp.next = prev; prev = temp; temp = copy; } return prev; } static void unfold(ListNode head) { // for segregating the original linked list into two // linked list on the basis of even and odd int i = 0; // For storing the previous node // and head node for each linked list ListNode prev1 = null, prev2 = null, h1 = head, h2 = head; while (head != null) { if (i % 2 == 0) { if (prev1 == null) { h1 = head; prev1 = head; } else { prev1.next = head; prev1 = head; } } else { if (prev2 == null) { h2 = head; prev2 = head; } else { prev2.next = head; prev2 = head; } } i++; head = head.next; } prev2.next = null; ListNode rev = reverse(h2); // reverse the second linked list prev1.next = rev; // join the first ll with second one } static void printList(ListNode node) { ListNode curr = node; while (curr != null) { System.out.print(curr.val + " "); curr = curr.next; } System.out.println(); } public static void main(String[] args) { int n; ListNode dummy = new ListNode(-1); ListNode prev = dummy; n = 5; int i = 0; int arr[] = { 1, 5, 2, 4, 3 }; // Elements in the linkedlist while (i < n) { prev.next = new ListNode(arr[i]); prev = prev.next; i++; } ListNode head = dummy.next; printList(head); unfold(head); printList(head); }}// This code is contributed by Lovely Jain |
Python3
# Python code to implement the above approachclass ListNode: def __init__(self,val): self.next = None self.val = valdef reverse(head): prev,temp,copy = None,head,None while (temp != None): copy = temp.next temp.next = prev prev = temp temp = copy return prevdef unfold(head): # for segregating the original linked list into two # linked list on the basis of even and odd i = 0 # For storing the previous node # and head node for each linked list prev1,prev2,h1,h2 = None,None,head,head while (head != None): if (i % 2 == 0): if (prev1 == None): h1 = head prev1 = head else : prev1.next = head prev1 = head else: if (prev2 == None): h2 = head prev2 = head else: prev2.next = head prev2 = head i += 1 head = head.next prev2.next = None rev = reverse(h2) # reverse the second linked list prev1.next = rev # join the first ll with second onedef printList(node): curr = node while (curr != None): print(curr.val,end = " ") curr = curr.next print()# driver codedummy = ListNode(-1)prev = dummyn=5i=0arr = [1, 5, 2, 4, 3] #Elements in the linkedlistwhile (i < n): prev.next = ListNode(arr[i]) prev = prev.next i += 1head = dummy.nextprintList(head)unfold(head)printList(head)# this code is contributed by shinjanpatra |
C#
// C# implementation of the approachusing System;class GFG { class ListNode { public int val = 0; public ListNode next = null; public ListNode(int val) { this.val = val; } } static ListNode reverse(ListNode head) { ListNode prev = null, temp = head, copy = null; while (temp != null) { copy = temp.next; temp.next = prev; prev = temp; temp = copy; } return prev; } static void unfold(ListNode head) { // for segregating the original linked list into two // linked list on the basis of even and odd int i = 0; // For storing the previous node and head node for // each linked list. ListNode prev1 = null, prev2 = null, h2 = head; while (head != null) { if (i % 2 == 0) { if (prev1 == null) { prev1 = head; } else { prev1.next = head; prev1 = head; } } else { if (prev2 == null) { h2 = head; prev2 = head; } else { prev2.next = head; prev2 = head; } } i++; head = head.next; } prev2.next = null; ListNode rev = reverse( h2); // reverse the second linked list. prev1.next = rev; // join the first linked list with // second one. } static void printList(ListNode node) { ListNode curr = node; while (curr != null) { Console.Write(curr.val + " "); curr = curr.next; } Console.WriteLine(); } static public void Main() { // Code int n; ListNode dummy = new ListNode(-1); ListNode prev = dummy; n = 5; int i = 0; int[] arr = { 1, 5, 2, 4, 3 }; // Elements in the linked list. while (i < n) { prev.next = new ListNode(arr[i]); prev = prev.next; i++; } ListNode head = dummy.next; printList(head); unfold(head); printList(head); }}// This code is contributed by lokesh (lokeshmvs21). |
Javascript
<script>// JavaScript code to implement the above approachclass ListNode { constructor(val){ this.next = null; this.val = val; }}function reverse(head){ let prev = null, temp = head, copy = null; while (temp != null) { copy = temp.next; temp.next = prev; prev = temp; temp = copy; } return prev;}function unfold(head){ // for segregating the original linked list into two // linked list on the basis of even and odd let i = 0; // For storing the previous node // and head node for each linked list let prev1 = null, prev2 = null, h1 = head,h2 = head; while (head != null) { if (i % 2 == 0) { if (prev1 == null) { h1 = head; prev1 = head; } else { prev1.next = head; prev1 = head; } } else { if (prev2 == null) { h2 = head; prev2 = head; } else { prev2.next = head; prev2 = head; } } i++; head = head.next; } prev2.next = null; let rev = reverse(h2); // reverse the second linked list prev1.next = rev; // join the first ll with second one}function printList(node){ let curr = node; while (curr != null) { document.write(curr.val," "); curr = curr.next; } document.write("</br>");}// driver codelet n;let dummy = new ListNode(-1);let prev = dummy;n=5;let i=0;let arr = [1, 5, 2, 4, 3]; //Elements in the linkedlistwhile (i < n) { prev.next = new ListNode(arr[i]); prev = prev.next; i++;}let head = dummy.next;printList(head);unfold(head);printList(head);// This code is contributed by shinjanpatra</script> |
Output
1 5 2 4 3 1 2 3 4 5
Time Complexity: O(N), where N is the total number of nodes in the linked list.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
