C# O(n) time O(1) space(reverse the first half)


  • 0
    Y
    /**
     * 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) {
            ListNode pre=null,slow=head,fast=head;
            while(fast!=null&&fast.next!=null)
            {
                fast=fast.next.next;
                var temp=slow.next;
                slow.next=pre;
                pre=slow;
                slow=temp;
            }
            if(fast!=null&&fast.next==null) 
                slow=slow.next;
            while(slow!=null)
            {
                if(slow.val!=pre.val)
                    return false;
                slow=slow.next;
                pre=pre.next;
            }
            return true;
            
        }
    }

Log in to reply
 

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