Программа для разворачивания сложенного связного списка
Опубликовано: 23 Января, 2022
Связанный список L 0 -> L 1 -> L 2 ->… .. -> L N может быть свернут как L 0 -> L N -> L 1 -> L N - 1 -> L 2 ->…. .
Учитывая свернутый связанный список, задача состоит в том, чтобы развернуть и распечатать исходный связанный список.
Примеры:
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
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: сделайте рекурсивный вызов и сохраните следующий узел во временном указателе, первый узел будет действовать как головной узел, а узел, который хранится во временном указателе, будет действовать как хвост списка. По возвращении после достижения базового состояния свяжите голову и хвост с предыдущей головой и хвостом соответственно.
Базовое условие: если количество узлов четное, то второй последний узел является головным, а последний узел - хвостовым, а если количество узлов нечетное, то последний узел будет действовать как головной, так и хвостовой.
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;}// Funcion 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(); } // Funcion 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 positio 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(); } // Funcion 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.
РЕКОМЕНДУЕМЫЕ СТАТЬИ |