我正在嘗試了解鏈表。但我對這個問題感到困惑。第一個代碼作業得很好。它反轉鏈表的一半并將其與另一部分進行比較。我完全明白。但是，當我反轉整個串列并將其與開頭指向它的串列進行比較時，它不起作用。
第一個代碼塊有效。
public bool IsPalindrome(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
// Point fast to original head. Works w/o any problem
fast=head;
slow=Reverse(slow);
while(slow!=null){
if(slow.val!=fast.val)
return false;
slow=slow.next;
fast=fast.next;
}
return true;
}
public ListNode Reverse(ListNode slow){
ListNode prev=null;
while(slow!=null){
ListNode next=slow.next;
slow.next=prev;
prev=slow;
slow=next;
}
return prev;
}
第二個代碼塊不起作用，盡管它做了幾乎相同的事情。我反轉整個串列并將其與指向原始 ListNode 頭的串列進行比較。我不修改 head 而是只修改 ListNode 慢。
public bool IsPalindrome(ListNode head) {
ListNode first=head;
ListNode second=head;
second=Reverse(second);
while(second!=null && first!=null){
if(second.val!=first.val)
return false;
second=second.next;
first=first.next;
}
return true;
}
public ListNode Reverse(ListNode slow){
ListNode prev=null;
while(slow!=null){
ListNode next=slow.next;
slow.next=prev;
prev=slow;
slow=next;
}
return prev;
}
uj5u.com熱心網友回復：
第二個版本不起作用，因為比較回圈假設您現在有兩個串列。但事實并非如此：反轉應用于串列本身，因此first參考現在將參考尾節點，其next參考為null。因此回圈將在第一次迭代后立即停止，就像first將變成null. 想一想：next每個節點只有一個參考，所以你不能指望在兩個相反的方向遍歷一個串列。
一種解決方案是進行調整，Reverse這樣它實際上會在不改變原始串列的情況下創建一個新串列。
uj5u.com熱心網友回復：
泰德。我在私人圖書館中有一個鏈接串列，并將其修改為有點像您的示例。這是一個雙向鏈接串列，因此您可以向前或向后導航 - 我在 ListNodeLinkedList 類上放置了一個 Reverse() 函式。我知道這與您的快/慢語言不完全一樣，但希望它會幫助您了解鏈表功能的要點。
class Program
{
static void Main(string[] args)
{
string palindrome = "madamimadam"; // madam I'm Adam - the first palindrome. :)
var linkedList = new ListNodeLinkedList();
foreach (char c in palindrome.ToCharArray())
{
linkedList.AddLast(new ListNode() { Character = c });
}
var reverse = linkedList.Reverse();
if (palindrome == reverse) { Console.WriteLine("success"); }
else { Console.WriteLine("failure"); }
// for the record, this is an arbitrary use of a linked list
// what we're doing here could also be done like this:
string copy = palindrome;
copy.Reverse();
if (palindrome == copy) { Console.WriteLine("simpler success"); }
else { Console.WriteLine("simpler failure"); }
}
}
class ListNode
{
public char Character { get; set; }
public ListNode Previous { get; set; }
public ListNode Next { get; set; }
}
class ListNodeLinkedList
{
private ListNode first = null;
private ListNode last = null;
public ListNodeLinkedList()
{ }
public ListNode First => first;
public ListNode Last => last;
public string Reverse()
{
List<char> list = new();
ListNode node = last;
while (node != null)
{
list.Add(node.Character);
node = node.Previous;
}
return new string(list.ToArray());
}
public void AddFirst(ListNode node)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
if (first == null)
{
first = node;
last = node;
}
else
{
node.Next = first;
node.Previous = null;
first = node;
}
}
public void AddLast(ListNode node)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
if (last == null)
{
first = node;
last = node;
}
else
{
node.Previous = last;
node.Next = null;
last.Next = node;
last = node;
}
}
public void AddAfter(ListNode node, ListNode newNode)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
if (newNode == null) { throw new ArgumentNullException(nameof(newNode)); }
if (last == node) { AddLast(newNode); }
else
{
newNode.Next = node.Next;
newNode.Previous = node;
node.Next = newNode;
newNode.Next.Previous = newNode;
}
}
public void AddBefore(ListNode node, ListNode newNode)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
if (newNode == null) { throw new ArgumentNullException(nameof(newNode)); }
if (first == node) { AddFirst(newNode); }
else
{
newNode.Previous = node.Previous;
newNode.Next = node;
node.Previous = newNode;
newNode.Previous.Next = newNode;
}
}
public void RemoveBefore(ListNode node)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
node.Previous = node.Previous?.Previous;
if (node.Previous != null)
{
node.Previous.Next = node;
}
if (node.Previous == null) { first = node; }
if (node.Next == null) { last = node; }
}
public static void RemoveAfter(ListNode node)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
node.Next = node.Next?.Next;
if (node.Next != null)
{
node.Next.Previous = node;
}
}
public void Remove(ListNode node)
{
if (node == null) { throw new ArgumentNullException(nameof(node)); }
if (node == first)
{
MakeNodeFirst(first.Next);
}
else if (node == last)
{
MakeNodeLast(node.Previous);
}
else
{
if (node.Previous != null)
{
node.Previous.Next = node.Next;
}
if (node.Next != null)
{
node.Next.Previous = node.Previous;
}
}
}
private void MakeNodeFirst(ListNode node)
{
first = node;
if (first != null)
{
first.Previous = null;
}
}
private void MakeNodeLast(ListNode node)
{
last = node;
if (last != null)
{
last.Next = null;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359118.html
上一篇：通過非常量，不斷地調整陣列的大小