在C#中反转单链表

Question

我正在尝试反转一个链表。这是我想到的代码:

 public static void Reverse(ref Node root)
 {
      Node tmp = root;
      Node nroot = null;
      Node prev = null;

      while (tmp != null)
      {
          //Make a new node and copy tmp
          nroot = new Node();    
          nroot.data = tmp.data;

          nroot.next = prev;
          prev = nroot;   
          tmp = tmp.next;
       }
       root = nroot;            
  }

它能够很好地工作。想知道是否可能避免创建新节点。希望得到相关建议。

- Nemo

---

你为什么要为此实现一个自定义集合？System.Collections 命名空间中的选项都不能满足你的需求吗？ - M.Babcock

我正在学习并准备面试。 - Nemo

Node 在哪个命名空间中？ - Dave Lawrence

Answer 1

这个问题经常被提出。当我多年前在面试中被问到时，我的思路如下：单项链表本质上就是一个栈。因此，在栈上反转链表就是一种微不足道的操作：

newList = emptyList;
while(!oldList.IsEmpty())
    newList.Push(oldList.Pop());

现在你只需要实现IsEmpty、Push和Pop，这最多只需要1-2行代码。我大约花了20秒钟写出来，面试官似乎有些困惑。我觉得他原本希望我用大约20分钟的时间来完成20秒钟的工作，这对我来说总是感觉很奇怪。

- Eric Lippert

---

@AdamRackis：这也是语法完美的 JavaScript、C++，可能还有其他几种编程语言。 :) - Eric Lippert

@Markus: 首先，我有所怀疑。其中一些解决方案非常长，每个堆栈操作都需要几行代码。而对于这种微不足道的代价，您可以获得一个堆栈ADT。在代码中使用抽象数据类型上的操作进行推理，而不是使用指针和变量，这样您的代码将变得更容易理解。如果面试官根据代码高尔夫来评判候选人，那么他正在寻找错误的信号。 - Eric Lippert

@Markus：在这里，让我们把它放进一个注释中。首先实现一个不可变的链表：class Node<T> { public T Head { get; private set; } public Node<T> Tail { get; private set; } public static Node<T> Empty = new Node<T>(); private Node() {} public Node<T> Push(T t) => new Node<T> { Head = t, Tail = this } } 现在我们实现一个可变的 class List<T> { private Node<T> n = Node<T>.Empty; public bool IsEmpty => n == Node<T>.Empty; public void Push(T t) { n = n.Push(t); } public T Pop() { T h = n.Head; n = n.Tail; return h; }} 就完成了。 - Eric Lippert

@Markus：现在我们有可变和不可变的堆栈。每种方法都介于一到三行代码之间，我们可以通过抽象操作来推理列表的行为，而不是通过引用和属性的实现方式。这不仅比这里发布的任何其他解决方案更全面，而且比大多数解决方案都要短，因为显然简洁是你关心的事情。 - Eric Lippert

当然，在一个适当的实现中，我们将遵守良好编程规范，在弹出一个空栈时会抛出异常，并在不可变栈上实现 IsEmpty 方法及其他增强功能。但是，使任何代码更加健壮和全面都会增加其长度。我在这里的意图并不是为了实现最短的健壮解决方案，而是要指出，当你将编程思路提高一个语义层级时，代码变得更短、更易理解 关键地方。 - Eric Lippert

Answer 2

Node p = root, n = null;
while (p != null) {
    Node tmp = p.next;
    p.next = n;
    n = p;
    p = tmp;
}
root = n;

- Sergey Kalinichenko

Answer 3

几年前我错过了一个嬉皮洛杉矶娱乐公司的ASP.NET MVC开发者职位，因为我无法回答这个问题 :( （这是一种淘汰非计算机科学专业人员的方法）。所以我很尴尬地承认，我在LINQpad中使用实际的LinkedList<T>花费了太长时间来弄清楚这个问题：

var linkedList = new LinkedList<int>(new[]{1,2,3,4,5,6,7,8,9,10});
linkedList.Dump("initial state");

var head = linkedList.First;
while (head.Next != null)
{
    var next = head.Next;
    linkedList.Remove(next);
    linkedList.AddFirst(next.Value);
}

linkedList.Dump("final state");

只读的LinkedListNode<T>.Next属性是使LinkedList<T>在这里如此重要的原因。(非计算机科学人员被鼓励研究数据结构的历史---我们应该问这个问题：链表从哪里来，为什么存在？)

- rasx

---

和你一样，上周我因为同样的问题（关于反转链表）错过了一个ASP.NET MVC开发者职位 :( - Andritchi Alexei

不错！虽然反转链表是一个通用问题，但在C#中实现它与C++或Java相比是不同且棘手的，因为C#的节点不允许设置下一个。所以你必须理解如何设置下一个并考虑删除！ - Higher-Kinded Type

Answer 4

您不需要复制。以下是一些伪代码:

prev = null;
current = head;
next = current->next;

(while next != null)
    current->next=prev
    prev=current
    current=next
    next=current->next

- ChrisWue

Answer 5

这在LeetCode上表现得相当不错。

public ListNode ReverseList(ListNode head) {

        ListNode previous = null;
        ListNode current = head; 
        while(current != null) {
            ListNode nextTemp = current.next;
            current.next = previous;
            previous = current;
            current = nextTemp;
        }

        return previous;
    }     

- Jack Marchetti

Answer 6

为什么不直接让头指向尾，尾指向头，然后通过列表反转prev指向的方向呢？

如果您没有使用头和尾，只需遍历列表并反转prev关系，然后将head指向到达时具有null prev的元素。

- Robert Allan Hennigan Leahy

Answer 7

这是一个反转链表的示例代码。

使用System命名空间。

class Program
{
    static void Main(string[] args)
    {
        LinkItem item = generateLinkList(5);
        printLinkList(item);
        Console.WriteLine("Reversing the list ...");
        LinkItem newItem = reverseLinkList(item);
        printLinkList(newItem);
        Console.ReadLine();
    }

    static public LinkItem generateLinkList(int total)
    {
        LinkItem item = new LinkItem();
        for (int number = total; number >=1; number--)
        {
            item = new LinkItem
            {
                name = string.Format("I am the link item number {0}.", number),
                next = (number == total) ? null : item
            };
        }
        return item;
    }

    static public void printLinkList(LinkItem item)
    {
        while (item != null)
        {
            Console.WriteLine(item.name);
            item = item.next;
        }
    }

    static public LinkItem reverseLinkList(LinkItem item)
    {
        LinkItem newItem = new LinkItem
        {
            name = item.name,
            next = null
        };

        while (item.next != null)
        {
            newItem = new LinkItem
            {
                name = item.next.name,
                next = newItem
            };

            item = item.next;
        }

        return newItem;
    }
}

class LinkItem
{
    public string name;
    public LinkItem next;
}

- Olev

Answer 8

public Node ReverseList(Node cur, Node prev)
    {
        if (cur == null) // if list is null
            return cur;

        Node n = cur.NextNode;
        cur.NextNode = prev;
        return (n == null) ? cur : ReverseList(n, cur);
    }

- Saboor Awan

---

cur似乎是根 - prev是什么？ - fubo

Answer 9

链表反转递归

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ReverseLinkedList
{
    class Program
    {
        static void Main(string[] args)
        {
            Node head = null;
            LinkedList.Append(ref head, 25);
            LinkedList.Append(ref head, 5);
            LinkedList.Append(ref head, 18);
            LinkedList.Append(ref head, 7);

            Console.WriteLine("Linked list:");
            LinkedList.Print(head);

            Console.WriteLine();
            Console.WriteLine("Reversed Linked list:");
            LinkedList.Reverse(ref head);
            LinkedList.Print(head);

            Console.WriteLine();
            Console.WriteLine("Reverse of Reversed Linked list:");
            LinkedList.ReverseUsingRecursion(head);
            head = LinkedList.newHead;
            LinkedList.PrintRecursive(head);
        }

        public static class LinkedList
        {
            public static void Append(ref Node head, int data)
            {
                if (head != null)
                {
                    Node current = head;
                    while (current.Next != null)
                    {
                        current = current.Next;
                    }

                    current.Next = new Node();
                    current.Next.Data = data;
                }
                else
                {
                    head = new Node();
                    head.Data = data;
                }
            }

            public static void Print(Node head)
            {
                if (head == null) return;
                Node current = head;
                do
                {
                    Console.Write("{0} ", current.Data);
                    current = current.Next;
                } while (current != null);
            }

            public static void PrintRecursive(Node head)
            {
                if (head == null)
                {
                    Console.WriteLine();
                    return;
                }
                Console.Write("{0} ", head.Data);
                PrintRecursive(head.Next);
            }

            public static void Reverse(ref Node head)
            {
                if (head == null) return;
                Node prev = null, current = head, next = null;
                while (current.Next != null)
                {
                    next = current.Next;
                    current.Next = prev;
                    prev = current;
                    current = next;
                }
                current.Next = prev;
                head = current;
            }

            public static Node newHead;

            public static void ReverseUsingRecursion(Node head)
            {
                if (head == null) return;
                if (head.Next == null)
                {
                    newHead = head;
                    return;
                }

                ReverseUsingRecursion(head.Next);
                head.Next.Next = head;
                head.Next = null;
            }
        }

        public class Node
        {
            public int Data = 0;
            public Node Next = null;
        }
    }
}

- Nisar

Answer 10

如果您需要一个现成的高效实现，我创建了一个替代LinkedList的方案，支持枚举和反转操作。https://github.com/NetFabric/NetFabric.DoubleLinkedList

- Antao Almada