The hard part is reverse the second part of linked list


  • 0
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while (fast.next != null) {
                slow = slow.next;
                if (fast.next.next == null) {
                    fast = fast.next;
                } else fast = fast.next.next;
            }
            
            // reverse the second half part of linked list
            ListNode newHead = null;
            ListNode head2 = slow.next;
            while (head2 != null) {
                ListNode next = head2.next;
                head2.next = newHead;
                newHead = head2;
                head2 = next;
            }
            
            while (newHead != null && head != null) {
                if (newHead.val != head.val) return false;
                head = head.next;
                newHead = newHead.next;
            }
            return true;
        }
    }
    

Log in to reply
 

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