Java --- reverse half list and compare


  • 0

    A straightforward solution

    public class Solution {
        public boolean isPalindrome(ListNode head) {
            
            int len = 0;
            ListNode runner = head;
            
            while(runner != null) {
                len++;
                runner = runner.next;
            }
            
            runner = head;
            int times = (len+1)/2;
            for(int i = 0; i < times; i++) {
                runner = runner.next;
            }
            
            //reverse runner
            ListNode newHead = null;
            while(runner != null) { // runner is not the last node
                ListNode next = runner.next;
                runner.next = newHead;
                newHead = runner;
                runner = next;
            }
            
            // compare head and runner
            while(newHead != null) {
                if(newHead.val != head.val) {
                    return false;
                }
                newHead = newHead.next;
                head = head.next;
            }
            return true;
        }
    }
    

Log in to reply
 

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