我正在尝试反转链接列表。这是我想出的代码：
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;
}
为什么不把 head 点放在尾部，tail 点放在头部，然后通过反转 prev 指向的方向的列表呢？
如果您不使用 head 和 tail，只需遍历列表反转 prev 关系，然后将 head 指向具有 null prev 的那个。
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;
}
}
}
复杂度 O(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)
此外，面试问题的美妙之处在于更少的内存消耗和到位的反转。也许还问了一种递归的方法。