Is Linked List Palindrome? Confused with Pointing

Question

I am trying to understand Linked Lists. But I am confused with this question. First code works just fine. It reverse the half of the linked list and compare it to the other part. I totally understand it. However, when I reverse the entire list and compare it to the list that was pointed to it at the beginning, it doesn't work.

First code block works.

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

Second code block doesn't work although it does pretty much the same thing. I reverse the entire list and compare it to the list that points to the original ListNode head. I do not modify head but ListNode slow only.

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

Ted. I had a linked list in a private library and modified it to be kinda like your example. This is a doubly-linked list, so that you can navigate forwards or back - I put a Reverse() function on the ListNodeLinkedList class. I know this isn't exactly like your fast/slow language, but hopefully, it'll help you see the gist of how linked lists function.

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

The second version does not work because the comparison loop assumes that you now have two lists. But that is not true: the reversal is applied to the list itself, and so the first reference will now be referencing the tail node, with its next reference being null. So the loop will stop immediately after the first iteration as first will have become null. Just think about it: there is just one next reference in each node, so you cannot expect to walk through one list in two opposite directions.

One solution is to adapt Reverse so it will actually make a new list without altering the original list.