反向打印链表,无需额外的空间和修改
原文:https://www.geeksforgeeks.org/print-reverse-linked-list-without-extra-space-modifications/
给定链表,以反向方式显示链表,而无需使用递归,栈或对给定列表的修改。
示例:
Input : 1->2->3->4->5->NULL
Output :5->4->3->2->1->NULL
Input :10->5->15->20->24->NULL
Output :24->20->15->5->10->NULL
下面是现在允许在此处使用的不同解决方案,因为我们不能使用额外的空间并修改列表。
-
反向打印链表的递归解决方案。 需要额外的空间。
-
反向链表,然后打印。 这需要修改原始列表。
-
用于反向打印链表的基于栈的解决方案。 将所有节点一个一个地推入栈。 然后从栈中逐一弹出元素并进行打印。 这也需要额外的空间。
算法:
1) Find n = count nodes in linked list.
2) For i = n to 1, do following.
Print i-th node using get n-th node function
C++
// C/C++ program to print reverse of linked list
// without extra space and without modifications.
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Counts no. of nodes in linked list */
int getCount(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}
/* Takes head pointer of the linked list and index
as arguments and return data at index*/
int getNth(struct Node* head, int n)
{
struct Node* curr = head;
for (int i=0; i<n-1 && curr != NULL; i++)
curr = curr->next;
return curr->data;
}
void printReverse(Node *head)
{
// Count nodes
int n = getCount(head);
for (int i=n; i>=1; i--)
printf("%d ", getNth(head, i));
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Use push() to construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printReverse(head);
return 0;
}
Java
// Java program to print reverse of linked list
// without extra space and without modifications.
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
};
static Node head;
/* Given a reference (pointer to pointer) to
the head of a list and an int, push a new node
on the front of the list. */
static void push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
head = head_ref;
}
/* Counts no. of nodes in linked list */
static int getCount(Node head)
{
int count = 0; // Initialize count
Node current = head; // Initialize current
while (current != null)
{
count++;
current = current.next;
}
return count;
}
/* Takes head pointer of the linked list and
index as arguments and return data at index*/
static int getNth(Node head, int n)
{
Node curr = head;
for (int i = 0; i < n - 1 && curr != null; i++)
curr = curr.next;
return curr.data;
}
static void printReverse()
{
// Count nodes
int n = getCount(head);
for (int i = n; i >= 1; i--)
System.out.printf("%d ", getNth(head, i));
}
// Driver Code
public static void main(String[] args)
{
/* Start with the empty list */
head = null;
/* Use push() to conbelow list
1->2->3->4->5 */
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
printReverse();
}
}
// This code is contributed by PrinciRaj1992
C
// C# program to print reverse of
// linked list without extra space
// and without modifications.
using System;
class GFG
{
/* Link list node */
public class Node
{
public int data;
public Node next;
};
static Node head;
/* Given a reference (pointer to pointer)
to the head of a list and an int, push a
new node on the front of the list. */
static void push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
head = head_ref;
}
/* Counts no. of nodes in linked list */
static int getCount(Node head)
{
int count = 0; // Initialize count
Node current = head; // Initialize current
while (current != null)
{
count++;
current = current.next;
}
return count;
}
/* Takes head pointer of the linked list and
index as arguments and return data at index*/
static int getNth(Node head, int n)
{
Node curr = head;
for (int i = 0;
i < n - 1 && curr != null; i++)
curr = curr.next;
return curr.data;
}
static void printReverse()
{
// Count nodes
int n = getCount(head);
for (int i = n; i >= 1; i--)
Console.Write("{0} ", getNth(head, i));
}
// Driver Code
public static void Main(String[] args)
{
/* Start with the empty list */
head = null;
/* Use push() to conbelow list
1->2->3->4->5 */
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
printReverse();
}
}
// This code is contributed by Princi Singh
输出:
5 4 3 2 1
如果您喜欢 GeeksforGeeks 并希望做出贡献,则还可以使用 tribution.geeksforgeeks.org 撰写文章,或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上,并帮助其他 Geeks。
如果您发现任何不正确的地方,请单击下面的“改进文章”按钮,以改进本文。
版权属于:月萌API www.moonapi.com,转载请注明出处