在C＃中反转单个链表

我试图扭转一个链表。 这是我提出的代码：

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

它运作良好。 想知道是否有可能避免创建新节点。 想对此有所建议。

Answer 1

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

Answer 2

这个问题被问了很多。 多年前我在采访中被问到这个问题时，我的理由如下：单链表基本上是一个堆栈。 因此，反转链表是堆栈上的一个简单操作：

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

现在你所要做的就是实现IsEmpty和Push and Pop，它们是一行或两行的顶部。

我在大约二十秒内把它写出来，面试官在这一点上似乎有些困惑。 我认为他希望我花大约20分钟做大约20秒的工作，这对我来说一直都很奇怪。

Answer 3

您无需复制。 一些伪代码：

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

Answer 4

几年前，我错过了一个时髦的洛杉矶娱乐公司ASP.NET MVC开发者职位，因为我无法回答这个问题：（（这是一种淘汰非计算机科学专业的方法。）所以我很尴尬承认我花了太长时间才使用实际的LinkedList在LINQpad中解决这个问题：

 var linkedList = new LinkedList(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.Next属性使LinkedList在这里如此重要。 （鼓励非comp-sci人研究数据结构的历史 – 我们应该问一个问题， 链表来自哪里—它为什么存在？）

Answer 5

为什么不只是在尾部的头部点，头部的尾点，并通过列表反转prev点的方向？

如果你没有使用头部和尾部，只需通过反转prev关系的列表，然后在你到达时使用null上一个的头部。

Answer 6

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

Answer 7

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

使用系统;

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

Answer 8

复杂度O（n + m）。 假设head是起始节点：

 ListNodes = new List(); 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; 

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

Answer 10

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

 public static void Reverse(Node root) 

此外，面试问题的美妙之处在于减少记忆消耗和逆转。 也许还会提出一种递归方式。