我想要反轉鏈表。這是我想出的代碼：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;
}
它運行良好。想知道是否有可能避免創建新節點。希望對此有所建議。
Node p = root, n = null;
while (p != null) {
Node tmp = p.next;
p.next = n;
n = p;
p = tmp;
}
root = n;
爲什麼不只是在尾巴的頭部點，頭部的尾部點，並通過列表逆轉prev指向的方向？
如果您不使用頭部和尾部，只需通過列表反轉prev關係，然後在您需要時指向具有空prev的頭部。
如何在O（N）中完成？ – Nemo 2011-12-31 04:05:51
這將是O（N）。 – 2011-12-31 04:11:38
您不需要複印。一些僞代碼：
prev = null;
current = head;
next = current->next;
(while next != null)
current->next=prev
prev=current
current=next
next=current->next
這個問題被問了很多。當我在多年前的訪談中被問及時，我推斷如下：單鏈表本質上是一個堆棧。因此倒車鏈表是堆一個簡單的操作：
newList = emptyList;
while(!oldList.IsEmpty())
newList.Push(oldList.Pop());
現在你需要做的就是實現的IsEmpty和push和pop，這是一個兩行頂部。
我在大約二十秒鐘內寫完了，面試官似乎有點困惑。我想他希望我花大約二十分鐘時間做大約二十秒鐘的工作，這對我來說總是很古怪。
+1 - 問題：您是否也必須確保'！='被重載，所以當'oldList'爲空時，它註冊爲'等於'emptyList'？ – 2011-12-31 05:05:27
@AdamRackis：當然。如果您願意，請將其更改爲'while（！oldList.IsEmpty（））'。這是僞代碼，不是任何語言的實際實現。 – 2011-12-31 05:06:41
Thanks @Eric - 你的僞代碼似乎在語法上完美的C＃，（這並不奇怪），所以我不得不問:) – 2011-12-31 05:08:11
裁判的定義是不必要的，因爲如果你做的節點作爲引用類型，這是確定的事情：
public static void Reverse(Node root)
此外，面試問題的美的記憶和地方消耗少逆轉。也許還會問一個遞歸的做法。
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);
}
cur似乎是根 - 什麼是prev？ – fubo 2015-06-08 12:05:10
幾年前，我錯過了一個時髦-LA-娛樂公司ASP.NET MVC開發者的位置，因爲我不能回答這個問題:(（這是淘汰非計算機科學專業的方法。 ）所以我不好意思地承認，我花了太長時間使用實際LinkedList<T>在LINQpad摸不着頭腦：
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>如此重要的位置（非CoMP -sci人被鼓勵研究數據結構的歷史---我們應該問這個問題，linked list來自---爲什麼它存在？）
和你一樣，上週我錯過了一個ASP.NET MVC開發人員職位，因爲關於反向鏈接列表的相同問題:( – 2015-01-27 18:24:48
好的！雖然反轉鏈接列表是一個普遍問題，但實現它的C＃是一個不同的相比於說C++或Java，因爲C＃的節點不允許接下來的設置，所以你必須讓你的頭在下一個設置，並考慮刪除！ – 2016-09-02 07:28:51
這裏是一個示例代碼來反轉鏈接列表。
using 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;
}
複雜度O（n + m）。假設頭開始節點：
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;
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;
}
}
}
你爲什麼要實施這個自定義集合？ 「System.Collections」命名空間中的任何選項都不能滿足您的要求嗎？ – 2011-12-31 04:01:44
我正在學習和準備面試。 – Nemo 2011-12-31 04:04:28
Node是什麼名字空間？ – 2016-12-15 16:42:44