C# solution with Stack O(N)/O(N)


  • 0
    S
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public bool IsPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            
            ListNode node = head;
            Stack<int> stack = new Stack<int>();
            bool firstHalfDone = false;
            while (node != null) {
                if (stack.Count > 0) {
                    if (stack.Peek() == node.val) {
                        if (!firstHalfDone) {
                            firstHalfDone = true;
                        }
                        stack.Pop();
                    } else {
                        if (firstHalfDone) {
                            return false;
                        } else {
                            // try pop. sometimes middle # doesn't matter.
                            int v = stack.Pop();
                            if (stack.Count > 0 && node.val == stack.Peek()) {
                                firstHalfDone = true;
                                stack.Pop();
                            } else {
                                stack.Push(v);
                            } 
                        }
                    }
                } else {
                    if (firstHalfDone) {
                        return false;
                    }
                }
                
                if (!firstHalfDone) {
                    stack.Push(node.val);
                }
                
                node = node.next;
            }
            
            if (firstHalfDone && stack.Count == 0) {
                return true;
            }
            
            return false;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.