链表是回文吗？与指向混淆

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 头的列表进行比较。我不修改头部，只修改 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

特德。我在私人图书馆中有一个链接列表，并将其修改为有点像您的示例。这是一个双向链表，因此您可以向前或向后导航 - 我在 ListNodeLinkedList class 上放置了一个 Reverse() 函数。我知道这与您的 fast/slow 语言不完全一样，但希望它能帮助您了解链表功能的要点。

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

Answer 2

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

一个解决方案是调整 Reverse 这样它实际上会在不改变原始列表的情况下创建一个新列表。

链表是回文吗？与指向混淆

Is Linked List Palindrome? Confused with Pointing

c#

algorithm

pointers

linked-list

data-structures