单向链表反转

Question

我猜这个问题是因为我对数据结构知识不足，但问题是如何反转单链表？我的印象是使用 "previous" 字段或属性来解决这个问题会使单链表成为双向链表，但我在网上找到的所有解决方案都涉及使用以前的属性。我在这里错过了什么？

Answer 1

您可以通过遍历重建列表。您 "pop" 输出的第一个元素将是结果中的最后一个元素，在伪代码中

new_list = nothing
while p != nothing:
    next = p.next
    p.next = new_list
    new_list = p
    p = next

Answer 2

假设单链表中的典型节点类似于：

class Node
{
    Node Next {get; set;}
    int Data {get; set;}
}

尝试反转这些列表时，可以做的一件有用的事情是想象一下您将如何做 "by hand"。例如，假设您有这个列表：

[head] 9 --> 3 --> 5 --> 1 --> 7 --> [null]

你会想做类似的事情

[null] <-- 9 <-- 3 <-- 5 <-- 1 <-- 7 [head]

如果我们从头到尾遍历列表，我们将从一个临时 "previous" 节点设置为 null（代表最后一个节点）和一个 "current" 节点设置为head，然后简单的把当前节点的"next"节点抓到一个变量里（以后用），把当前item的下一个属性指向"previous"节点，然后设置我们的"previous"节点到当前节点，当前节点到当前节点的原下一个节点。

换句话说：

Node previous = null;
Node current = head;

while (current != null)
{
    Node next = current.Next;  // capture the next node so we can change it 
    current.Next = previous;   // point this node's next to the previous node
    previous = current;        // update variable for next iteration
    current = next;            // update variable for next iteration
}

head = previous;               // finally we can update the head pointer

单向链表反转

Singly linked list reversal

c#

singly-linked-list