234. Palindrome Linked List

Question

Given the head of a singly linked list, return true if it is a palindrome.

Solution 1

快慢指针，快指针遍历到底时慢指针正好到一半。
根据快指针的位置判断奇数个还是偶数个。
如果是奇数个则翻转链表时需要向前移动一位。

接下来翻转后半段链表。
翻转完成后从第一段的头部和翻转过的链表头部开始遍历。
如果两个节点的值不同则返回false。

遍历完毕返回true。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode slow = head, fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode curr = fast == null ? slow : slow.next, prev = null;   //make sure curr is the head of the 2nd part
        
        while(curr != null){    //reverse the 2nd part of the nodes
            ListNode temp = curr.next; //preserve nodes that after current node
            curr.next = prev; //add previous node to the current node's next
            prev = curr; //save previous node
            curr = temp; //update current node
        }
        
        while(head != null && prev != null){
            if(head.val != prev.val) return false;
            prev = prev.next;
            head = head.next;
        }
        return true;
    }
}

Solution 2

快慢指针的原理，不是记录长度而是当快指针遍历到链表尾时停止。
然后对照栈内的值是否和剩余的值相等。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        Stack<ListNode> stack = new Stack<>();

        while(fast != null && fast.next != null){
            stack.add(slow);

            slow = slow.next;
            fast = fast.next.next;
        }
        
        if(fast != null) slow = slow.next;
        
        while(!stack.isEmpty()){
            if(stack.pop().val != slow.val) return false;
            slow = slow.next;
        }
        
        return true;
    }
}

Solution 3

回文，先计算链表长度。
记录链表长度是否为奇数。

如果链表长度为偶数，则将一半的节点放入栈中。
如果为奇数则抛弃一个节点。
剩下一半的节点和栈顶节点比较，如果值不相同则返回false。

遍历完成返回true。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode root = head;
        Stack<ListNode> stack = new Stack<>();
        
        while(root != null){
            root = root.next;
            len++;
        }
        
        root = head;
        for(int i = 0; i < len/2; i++){
            stack.add(root);
            root = root.next;
        }
        
        if(len % 2 != 0) root = root.next;
        
        for(int i = 0; i < len/2; i++){
            if(stack.peek().val == root.val) stack.pop();
            else return false;
            root = root.next;
        }
        return true;
    }
}