234.回文链表¶

题目描述¶

请判断一个链表是否为回文链表。

示例 1:

1 2	`输入: 1->2 输出: false`

示例 2:

1 2	`输入: 1->2->2->1 输出: true`

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题解¶

/**
 * 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) {
        //考虑特殊情况
        if (head == null) {
            return true;
        }

        //1.找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        //2.判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        //这里p1是从头走的 p2是从一半走的，所以只需要判断p2
        while (result && p2 != null) {
            result = p1.val == p2.val;
            p1 = p1.next;
            p2 = p2.next;
        }        

        //3.还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    //类似于找倒数第几个数 这里不过是找中间位置
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}