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;            
  }

这个问题经常被问到。当我在多年前的采访中被问到这个问题时，我的推理如下:单链表本质上是一个堆栈。因此，反转链表是栈上的一个微不足道的操作:

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

现在你所要做的就是实现IsEmpty, Push和Pop，这是一到两行。

我用了大约20秒的时间写了出来，面试官在这一点上似乎有些困惑。我想他希望我花20分钟做20秒的工作，这对我来说一直很奇怪。

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

几年前我错过了一个潮人洛杉矶。娱乐公司的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>在这里如此重要。(鼓励非比较科学的人研究数据结构的历史——我们应该问这样的问题，链表来自哪里——它为什么存在?)

你不需要做一个副本。一些伪代码:

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

这在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;
    }     

为什么不让头部指向尾部，尾部指向头部，然后将前面指向的方向反向浏览列表呢?

如果你没有使用正面和尾部，只需通过列表反转前置关系，然后使头部指向有一个空前置当你到达它。

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);
    }

下面是反转链表的示例代码。

使用系统;

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;
}

链表反转递归

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;
        }
    }
}

复杂度0 (n+m)。假设head为起始节点:

List<Node>Nodes = new List<Node>();
Node traverse= root;
while(traverse!=null)
{      
       Nodes.Add(traverse);
       traverse = traverse.Next;
}
int i = Nodes.Count - 1;     
root = Nodes[i];
for(; i>0; i--)
{
  Nodes[i].Next = Nodes[i-1];
}
Nodes[0].Next=null;

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

    public class Node<T>
    {
        public T Value { get; set; }
        public Node<T> Next { get; set; }
    } 
    public static Node<T> Reverse<T>(Node<T> head)
    {
        Node<T> tail = null;
        while(head!=null)
        {
            var node = new Node<T> { Value = head.Value, Next = tail };
            tail = node;
            head = head.Next;
        }
        return tail;
    }

ref的定义是不必要的，因为如果您将节点作为引用类型，则可以这样做:

public static void Reverse(Node root)

同时，面试问题的美妙之处在于较少的记忆消耗和位置反转。也许还需要递归的方法