题解 | #判断一个链表是否为回文结构#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public boolean isPail (ListNode head) {
        boolean a = true;
        // 复制原始链表
        ListNode originalHead = copyList(head);
        ListNode cur = head, pre, next;
        pre = null;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        while (originalHead != null && pre != null) {
            if (originalHead.val != pre.val) {
                return false;
            }
            originalHead = originalHead.next;
            pre = pre.next;
        }
        return a;
        // write code here
    }
    // 辅助函数：复制链表
    private ListNode copyList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode newHead = new ListNode(head.val);
        ListNode cur = newHead;
        while (head.next != null) {
            head = head.next;
            cur.next = new ListNode(head.val);
            cur = cur.next;
        }

        return newHead;
    }
}

思路还是很简单的，就是把原链表反转，将原链表的值与反转后链表的值进行比较即可。我犯错的地方主要是忘记了链表是一种指向内存地址的引用，因此如果head=cur;cur.next=null;那么head也指向null了。因此在反转后head实际上仅是反转后链表的最后一个值了。因此，在反转后原链表其实已经不存在了，必须提前将其复制才行。复制也很简单，就是读取原链表的值，读一个就把一个值装入新创建的节点的指向，即 cur.next = new ListNode(head.val);