从给定的 LinkedList 在 C++ 中创建一个反向 LinkedList
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4908193/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Create a reverse LinkedList in C++ from a given LinkedList
提问by Xeo
I'm having some trouble create a linkedlist in reverse order from a given linkedlist.
我在从给定的链表以相反的顺序创建链表时遇到了一些麻烦。
I come from a java background, and just started doing some C++.
我来自 Java 背景，刚开始做一些 C++。
Can you check out my code and see what's wrong? I'm guessing I'm just manipulating pointer and not creating anything new.
你能看看我的代码，看看有什么问题吗？我猜我只是在操纵指针而不是创造任何新东西。
//this is a method of linkedlist class, it creates a reverse linkedlist
//and prints it
void LinkedList::reversedLinkedList()
{
Node* revHead;
//check if the regular list is empty
if(head == NULL)
return;
//else start reversing
Node* current = head;
while(current != NULL)
{
//check if it's the first one being added
if(revHead == NULL)
revHead = current;
else
{
//just insert at the beginning
Node* tempHead = revHead;
current->next = tempHead;
revHead = current;
}
current = current->next;
}//end while
//now print it
cout << "Reversed LinkedList: " << endl;
Node* temp = revHead;
while(temp != NULL)
{
cout << temp->firstName << endl;
cout << temp->lastName << endl;
cout << endl;
temp = temp->next;
}
}//end method
回答by Xeo
Easier one: Go through your linked list, save the previous and the next node and just let the current node point at the previous one:
更简单的一个：遍历你的链表，保存上一个和下一个节点，让当前节点指向上一个：
void LinkedList::reversedLinkedList()
{
if(head == NULL) return;
Node *prev = NULL, *current = NULL, *next = NULL;
current = head;
while(current != NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// now let the head point at the last node (prev)
head = prev;
}
回答by Xeo
Node* revHead;
// ...
while(current != NULL)
{
//check if it's the first one being added
if(revHead == NULL)
You don'tinitialize revHeadbut you use it.
(I hope it is already clear to you that revHeadis a local variable used to store a memory address, and not something that exists outside the method/procedure)
你不初始化，revHead但你使用它。（我希望你已经清楚这revHead是一个用于存储内存地址的局部变量，而不是存在于方法/过程之外的东西）
The Storage Class of revHeadis automatic (aka in the local scope-body). In C++when you do a declaration like that, there is not guarantee that the value will be 0.
的存储类revHead是自动的（又名在本地作用域主体中）。在C++当你做这样的声明，没有保证的价值会0。
(unless the storage class is of type staticor the variable is globalwhere it is automatically initialized to 0if no other value is provided. In your case the variable has storage class of type autowhich means it is locally defined in a function, and when declaring a local variable, without specifying a value, the value is garbage. Keep in mind that with the next C++ Standard C++0xthe keyword autohas a new meaning).
（除非存储类是类型static或变量是global在0没有提供其他值的情况下自动初始化的位置。在您的情况下，变量具有类型的存储类，auto这意味着它是在函数中本地定义的，并且在声明本地时变量，没有指定值，该值是垃圾。请记住，在下一个 C++ 标准中C++0x，关键字auto有了新的含义）。
The value in your case is garbage which makes the iffail. See more Information here : Link
在您的情况下，价值是垃圾，if导致失败。在此处查看更多信息：链接
Do a
做一个
Node* revHead = NULL;
Keep in mind that maybe you may have errors like that in other part of your code as well.
请记住，您的代码的其他部分可能也有类似的错误。
回答by Sundus
Another method would be to first traverse the list and store all data in a stack,then create a new list and insert data in it from top of the stack.Stack being LIFO will give you the data in reverse order and hence you will have a reversed list.
另一种方法是首先遍历列表并将所有数据存储在堆栈中，然后创建一个新列表并从堆栈顶部插入数据。堆栈是 LIFO 将以相反的顺序为您提供数据，因此您将有一个反转列表。
回答by Aditya Sastry
This is done using just two temporary variables.
这仅使用两个临时变量即可完成。
Node* list::rev(Node *first)
{
Node *a = first, *b = first->next;
while(a->next!=NULL)
{
b = a->next;
a->next = a->next->next;
b->next = first;
first = b;
}
return first;
}
Also, you can do this using recursion.
此外，您可以使用递归来做到这一点。
回答by knockoutrose
I'm not sure, but I think you want a doubly linked list where the node has a next and previous. It will not work using an external pointer to the list. You will not have the address of the previous node.
我不确定，但我认为你想要一个双向链表，其中节点有下一个和上一个。使用指向列表的外部指针将不起作用。您将没有前一个节点的地址。
If not use the method above with a stack it's a good suggestion.
如果不将上述方法与堆栈一起使用，这是一个很好的建议。
回答by user3035654
The above is a reverse of Link List
以上是Link List的反面
void LinkList::rev()
{
if(pFirst == NULL) return;
ListElem *prev = NULL, *current = NULL, *next = NULL;
current = pFirst;
while(current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// now let the head point at the last node (prev)
pFirst = prev;
}
回答by user3035654
The sample below use the recursion for reversing a linklist. I asked this Qs at a job interview. This has been tested and works. ListElem is the node.
下面的示例使用递归来反转链接列表。我在求职面试中问了这个问题。这已经过测试并且有效。ListElem 是节点。
void LinkList::reverse()
{
if(pFirst == NULL) return;
ListElem* current = pFirst;
revCur(NULL, current, NULL);
}
void LinkList::revCur(ListElem *prev, ListElem* current, ListElem* next)
{
// ListElem *prev = NULL, *current = NULL, *next = NULL;
if ( current != NULL )
{
next = current->next;
current->next = prev;
prev = current;
current = next;
pFirst = prev;
this->revCur(prev,current,next);
}
}
回答by 010101010101kakaka92
#include <stdint.h>
/*
this is a generic (structure agnostic) routine for reversing a singly linked list.
1st argument is the memory address the structure is located at, and
2nd argument is the memory address to this particular structure's NEXT member.
*/
void *rsll(void *struct_address, void *next_address /*(void **)*/)
{
uint32_t offset, holder;
offset = next_address - struct_address;
void **p = struct_address, *progress = NULL;
while(p)
{
void *b;
holder = (uint32_t)p;
holder += offset;
p = (void**)holder; //&(N->next)
b = *p; //(N->next)
*p = progress; //(N->next)
holder = (uint32_t)p;
holder -= offset;
p = (void**)holder; //N
progress = p;
p = b;
}
return progress;
}
#include <stdio.h>
int
main()
{
struct list_t
{
int integer;
struct list_t *next;
};
struct list_t d = {40,NULL},
c = {30,&d},
b = {23,&c},
a = {10,&b};
struct list_t *list;
list = &a;
list = rsll(list,&(list->next));
while(list)
{
printf("%d\n",list->integer);
list = list->next;
}
return 0;
}
回答by Yiliang
NODE * ReverseLinkedList(NODE * head){
if (head == NULL)
return NULL;
NODE * previous = NULL;
while (head != NULL) {
// Keep next node since we trash the next pointer.
NODE *next = head->pNext;
// Switch the next pointer to point backwards.
head->pNext = previous;
// Move both pointers forward.
previous = head;
head = next;
}
return previous;
}
