c# solution, O(n) time, O(1) space, modifies original linked list


  • 0
    M
     public bool IsPalindrome(ListNode head) {
             if (head == null) return true;
                if (head.next == null) return true;
    
                ListNode current = head;
                int length = 0;
                while (current != null)
                {
                    current = current.next;
                    length++;
                }
    
                current = head;
                ListNode prev = null;
                ListNode next;
    
                for (int i = 0; i < length / 2; i++)
                {
                    next = current.next;
                    current.next = prev;
                    prev = current;
                    current = next;
                }
    
                ListNode head1 = prev;
                ListNode head2 = length % 2 == 1 ? current.next : current;
    
                while (head1 != null && head2 != null)
                {
                    if (head1.val != head2.val) return false;
                    head1 = head1.next;
                    head2 = head2.next;
                }
    
                return head1 == head2;
        }
    

Log in to reply
 

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