Share my solution with clear explanation


  • 0
    M
       /* For example, a list with odd nodes. After finding the middle node.
       1   ->   2   ->   3   ->   4   ->   3   ->   2   ->   1
       ↑                 ↑        ↑                          ↑
      head            preSlow   slow(middle)                fast
      */
    
    public boolean isPalindrome(ListNode head) {
                if (head == null || head.next == null) return true;
                ListNode slow = head, fast = head, preSlow = null;
                // firstly, find the middle node and its previous one.
                while (fast != null && fast.next != null) {
                    preSlow = slow;
                    slow = slow.next;
                    fast = fast.next.next;
                }
                preSlow.next = null;
                if (fast != null) // number of nodes is odd
                    slow = slow.next;
                // secondly, reverse the former half part.
                ListNode cur = head, tail = null;
                while (cur != null) {
                    ListNode nxt = cur.next;
                    cur.next = tail;
                    tail = cur;
                    cur = nxt;
                }
                // finally, just determine whether two nodes' values are equal.
                while (tail != null && slow != null) {
                    if (tail.val != slow.val) return false;
                    tail = tail.next;
                    slow = slow.next;
                }
                return true;
            }

Log in to reply
 

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