Share my accepted C# solution with comments O(n) time O(1) space


  • 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) {

        if(head==null || head.next==null)
        {
            return true;
        }
        
        //traverse and reverse the first half
        
        ListNode newHeader=new ListNode(0);
        newHeader.next=head;
        var next = head;
        var fast = newHeader;
        
        while(fast != null && fast.next != null)
        {
            fast = fast.next.next;
            var temp = next.next;
            next.next = newHeader;
            newHeader = next;
            next = temp;
        }
        
        //traverse and compare the first and second half
        //check odd and even
        
        if(fast==null)
        {
            newHeader = newHeader.next;
        }
        
        while(next!=null)
        {
            if(next.val != newHeader.val)
                return false;
            next = next.next;
            newHeader = newHeader.next;
        }
        
        
        return true;
      }
    

    }


Log in to reply
 

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