234. 回文链表

题目：

234. 回文链表

题解：

1. 题解一：

快指针走到末尾，慢指针刚好到中间，其中慢指针将前半部分反转，然后比较反转后的前半部分与原来的后半部分是否相同。

2. 题解二：

其一，find mid node 使用快慢指针找到链表中点。 其二，reverse 逆序后半部分。 其三，check 从头、中点，开始比较是否相同。

偶数节点情况：

奇数节点情况：

代码：

1. 代码一：

public class code234 {

    public static boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
        {
            return true;
        }
        /* 定义快慢两个指针 */
        ListNode slow = head;
        ListNode fast = head;
        /* 虚拟指针 */
        ListNode cur = head;
        ListNode pre = null;
        /* 找中点的时候完成反转 */
        // 快指针走到末尾，慢指针刚好到中间。其中慢指针将前半部分反转。（偶数个链表）
        while(fast != null && fast.next != null)
        {
            cur = slow;
            slow = slow.next;
            fast = fast.next.next;
            cur.next = pre;
            pre = cur;
        }
        /* 奇数个链表 */
        if(fast != null)
        {
            slow = slow.next;
        }
        // 然后比较反转后的前半部分与原来的后半部分是否相同
        while(cur != null && slow != null)
        {
            if(cur.val != slow.val)
            {
                return false;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }

    private static ListNode createLinkedList(int[] arr) {// 将输入的数组输入到链表中
        if (arr.length == 0) {
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {// 过程
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    private static void printLinkedList(ListNode head) {// 将链表结果打印
        ListNode current = head;
        while (current != null) {
            System.out.printf("%d -> ", current.val);
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        int[] x = { 1, 2, 2, 1 };
        ListNode list = createLinkedList(x);
        printLinkedList(list);
        boolean res = isPalindrome(list);
        System.out.println(res);
    }
}

2. 代码二：

public boolean isPalindrome(ListNode head) {
       if (head == null) {
           return true;
       }
       //通过快慢指针找到链表的中间节点
       ListNode slow=head;
       ListNode fast=head;
       while (fast!=null&&fast.next!=null){
           slow=slow.next;
           fast=fast.next.next;
       }

       ListNode pre=null;
       while (slow!=null){
           ListNode temp=slow.next;
           slow.next=pre;
           pre=slow;
           slow=temp;
       }

       while (head!=null&&pre!=null){
           if(head.val!=pre.val){
               return false;
           }else {
               pre=pre.next;
               head=head.next;
           }
       }
       return true;
   }

参考：

1. 我的快慢指针都从头开始，感觉更好理解
2. C++ 使用数组&反转链表
3. 234.java 双指针 图解！
4. 动画演示 234. 回文链表
5. 【回文链表】两种方法，详细图解
6. 回文链表
7. 回文链表（1.栈，2.快慢指针+翻转）
8. java，通俗易懂，原地进行，没有额外空间