リンクされたリストを逆にしようとしています。これは私が思いついたコードです:
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 を実装するだけです。これらは 1 行または 2 行の上部です。
私はそれを約20秒で書きましたが、インタビュアーはその時点でやや困惑しているように見えました. 彼は、私が約 20 秒の仕事をするのに約 20 分かかることを期待していたと思います。
Node p = root, n = null;
while (p != null) {
Node tmp = p.next;
p.next = n;
n = p;
p = tmp;
}
root = n;
数年前、私はこの質問に答えることができなかったために、流行に敏感な LA のエンターテイメント企業である 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>(comp-sci 以外の人々は、データ構造の歴史を研究することをお勧めします---リンク リストはどこから来たのか --- それはなぜ存在するのかという質問をすることになっています)。
コピーを作成する必要はありません。擬似コード:
prev = null;
current = head;
next = current->next;
(while next != null)
current->next=prev
prev=current
current=next
next=current->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;
}
}
}
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;
}
ノードを参照型として作成する場合は、次のことを実行しても問題ないため、refの定義は不要です。
public static void Reverse(Node root)
また、面接の質問の美しさは、記憶の消費が少なく、場所が逆転することです。たぶん、それを行う再帰的な方法も求められます。