Una lista enlazada L 0 -> L 1 -> L 2 -> ….. -> L N se puede plegar como L 0 -> L N -> L 1 -> L N – 1 -> L 2 -> …. Dada una lista enlazada plegada ,
la tarea es desplegar e imprimir la lista enlazada original
Ejemplos:
Entrada: 1 -> 6 -> 2 -> 5 -> 3 -> 4
Salida: 1 2 3 4 5 6Entrada: 1 -> 5 -> 2 -> 4 -> 3
Salida: 1 2 3 4 5
Enfoque: realice una llamada recursiva y almacene el siguiente Node en el puntero temporal, el primer Node actuará como Node principal y el Node que se almacena en el puntero temporal actuará como la cola de la lista. Al regresar después de alcanzar la condición base, vincule la cabeza y la cola con la cabeza y la cola anteriores, respectivamente.
Condición base: si el número de Nodes es par, el penúltimo Node es cabeza y el último Node es cola y si el número de Nodes es impar, el último Node actuará como cabeza y cola.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Node Class
struct Node
{
int data;
Node *next;
};
// Head of the list
Node *head;
// Tail of the list
Node *tail;
// Function to print the list
void 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 list
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
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
int 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 approach
public 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 Class class Node: def __init__(self, data): self.data = data self.next = None # Head of the list head = None # Tail of the list tail = None # Function to print the list def display(): if (head == None): return temp = head while (temp != None): print(temp.data, end = " ") temp = temp.next print() # Function to add node in the list def 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 list def 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 code if __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 approach
using 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 list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Head of the list
var head = null;
// Tail of the list
var tail = null;
// Function to print the list
function 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 list
function 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 list
function 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 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 jana_sayantan.
</script>
Producción
1 5 2 4 3 1 2 3 4 5
Complejidad de tiempo : O(N), donde N es el número total de Nodes en la lista enlazada.
Espacio Auxiliar: O(N)
Enfoque iterativo:-
Enfoque : Primero tenemos que segregar la lista enlazada sobre la base del índice par-impar. Luego invertimos la parte impar de la lista segregada y la unimos con la primera lista. Este enfoque no utiliza el espacio recursivo.
A continuación se muestra la implementación del enfoque anterior:
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 approach
class 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 approach class ListNode: def __init__(self,val): self.next = None self.val = val def reverse(head): prev,temp,copy = None,head,None while (temp != None): copy = temp.next temp.next = prev prev = temp temp = copy return prev def 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 one def printList(node): curr = node while (curr != None): print(curr.val,end = " ") curr = curr.next print() # driver code dummy = ListNode(-1) prev = dummy n=5 i=0 arr = [1, 5, 2, 4, 3] #Elements in the linkedlist while (i < n): prev.next = ListNode(arr[i]) prev = prev.next i += 1 head = dummy.next printList(head) unfold(head) printList(head) # this code is contributed by shinjanpatra
C#
// C# implementation of the approach
using 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 approach
class 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 code
let n;
let dummy = new ListNode(-1);
let prev = dummy;
n=5;
let i=0;
let arr = [1, 5, 2, 4, 3]; //Elements in the linkedlist
while (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>
Producción
1 5 2 4 3 1 2 3 4 5
Complejidad de tiempo: O(N), donde N es el número total de Nodes en la lista enlazada.
Espacio Auxiliar: O(1)