链表是回文的吗?与指点混淆

Question

我正在努力理解链表。但我对这个问题感到困惑。第一个代码运行良好。它反转链接列表的一半，并将其与另一部分进行比较。我完全理解。然而，当我颠倒整个列表并将其与一开始指向它的列表进行比较时，它不起作用。

第一个代码块工作。

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

Answer 1

第二个版本不起作用，因为比较循环假设您现在有两个列表。但事实并非如此：反转应用于列表本身，因此first引用现在将引用尾部节点，其next引用为null。因此，循环将在第一次迭代后立即停止，因为first将变为null。想想看：每个节点中只有一个next引用，所以不能期望在两个相反的方向上遍历一个列表。

一种解决方案是调整Reverse，使其在不更改原始列表的情况下实际生成新列表。

Answer 2

Ted。我在一个私人图书馆里有一个链接列表，并将其修改为有点像你的例子。这是一个双链接列表，因此您可以向前或向后导航-我在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;
}
}
}