One time traverse Java solution


  • 1
    W
    public class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while(fast!=null&&fast.next!=null){//Using fast-slow pointer to get the middle node
            fast = fast.next.next;
            ListNode temp = slow.next;
            slow.next = prev;//reverse the nodes between head and the middle node
            prev = slow;
            slow = temp;
        }
        if(fast!=null) slow = slow.next;
        fast = prev;
        while(true){
            if(slow==null&&fast==null) return true;
            if(slow==null||fast==null) return false;
            if(slow.val==fast.val){
                slow = slow.next;
                fast = fast.next;
            }else return false;
        }
    }
    

    }


  • 0
    L

    Idea is nice, but I don't think it's actually one pass, as you are doing more than one thing for each step of the loop.


Log in to reply
 

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