C# O(n) Runtime O(1) Space


  • 0
    K
     * 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;
            
            int length = GetLength(head);
            
            // reverse first half of list 
            ListNode prev = null;
            ListNode curr = head;
            for(int i = 0; i < length/2; ++i){
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            
            head.next = curr;
            ListNode fast = curr;
            curr = prev;
            if (length % 2 != 0){
                fast = fast.next;
            }
            
            while (fast != null){
                if (fast.val != curr.val)
                    return false;
                    
                fast = fast.next;
                curr = curr.next;
            }
            
            return true;
        }
        
        private int GetLength(ListNode head){
            int length = 0;
            while(head != null){
                length++;
                head = head.next;
            }
            return length;
        }
    }

Log in to reply
 

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