I am new to programming and today I wanted to try out the LeetCode problem 234. Palindrome Linked List:

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

but I couldn't even manage the first problem.

I first tried to convert the linked list to a string and compare like:

String[i] == String[length-i-1]

which worked for small lists but not for the gigantic test list where I got:

Time Limit Exceeded

In my second attempt I used recursion like this:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
    bool isPalindrome(ListNode? head) {
        ListNode? current = head;
  
        while(current?.next != null)      
            current = current?.next;
           
        if (current?.val != head?.val)
            return false;      
        else{          
            current = null;
            isPalindrome(head?.next);
        }
        return true;
    }       
}

This also works with small lists, but for the test list I get a run time error:

Stack overflow

I wonder where this issue comes from.

Is it due to the maximum number of nested calls? And where can I find the recursion depth of Dart? Or is there just a way simpler solution for this?

CodePudding user response：

There are several issues with your attempt:

• current = null will only set that variable to null. It does not affect the list. If you want to remove the last element from the list, you'll need access to the node that precedes it, and set its next property to null.

• The boolean that the recursive call returns is always ignore. Instead execution continues with the return true statement, which will lead to incorrect results (when false was expected).

Before mentioning another problem, here is the correction for your algorithm:

    bool isPalindrome(ListNode? head) {
        ListNode? current = head;
        ListNode? prev = null;
        while(current?.next != null) {
            prev = current; // follow behind current
            current = current?.next;
        }
        if (current?.val != head?.val)
            return false;      
        else if (prev == null)
            return true; // List has only one node
        else {
            prev?.next = null; // Detach the tail node
            return isPalindrome(head?.next); // Return the recursive result!
        }
    }

This will do the job correctly, but it is too slow. At every level of recursion almost all of the same nodes are iterated again (with that while loop), so for a list with 100 nodes, there are 100 98 96 94 ... 2 iterations. In other words, the time complexity of this algorithm is quadratic. You'll need a different idea for the algorithm.

One idea for an efficient algorithm that doesn't require extra O(n) space, is to:

• find the middle node of the list. You can for instance first determine the length of the list with a first iteration, and then in a second iteration you can stop half way.

• reverse the second half of the list, giving you two shorter lists. Here you could use recursion if you wanted to.

• and then compare those two lists node by node.

There are several Q&A on this algorithm, also on this site, so I'll leave that for your further research.

If you cannot make it work, here is a solution (spoiler!):

class Solution { int listSize(ListNode? head) { int size = 0; while(head?.next != null) { head = head?.next; size ; } return size; } ListNode? nodeAt(ListNode? head, int index) { while(head?.next != null && index > 0) { head = head?.next; index--; } return index == 0 ? head : null; } ListNode? reverse(ListNode? head) { ListNode? prev = null; ListNode? next; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } bool isEqual(ListNode? head1, ListNode? head2) { // Only compares the nodes that both lists have: while (head1 != null && head2 != null) { if (head1.val != head2.val) return false; head1 = head1.next; head2 = head2.next; } return true; } bool isPalindrome(ListNode? head) { return isEqual(head, reverse(nodeAt(head, listSize(head) >> 1))); } }

CodePudding user response：

I can't quite understand your recursion solution without pointers. I solved it using a list. It is not the best solution but is simple.

 //  Definition for singly-linked list.
//   class ListNode {
//     int val;
//     ListNode? next;
//     ListNode([this.val = 0, this.next]);
//   }
 
class Solution {
  bool isPalindrome(ListNode? head) {
    List<int> stack = [];
    ListNode? p = head;

    while (p != null) {
      stack.add(p.val);
      p = p.next;
    }
    print(stack);
    bool isP = true;
    
    while(head!.next!=null&&isP){
      var a = stack.removeLast();
      print('removed $a');
      print('head val ${head.val}');
      isP = head.val==a;
      head=head.next!;
    }
    return isP;
  }
}

The problem with your solution is

After a while loop current is rightmost node in the list

    while (current?.next != null) {
      current = current?.next;
    }

comparing leftmost and rightmost node of LinkedList

    if (current?.val != head?.val)
      return false;

Start over with head shifted one place to the right

    else {
      current = null;
      isPalindrome(head?.next);
}

But current is still rightmost node after a while loop

 while (current?.next != null) {
      current = current?.next;
    }

And this will return false

 if (current?.val != head?.val)
    {
      return false;
    }

After second recursion program exits returning true