[LeetCode Hot 100] LeetCode234. 回文链表

题目描述

思路1：将值复制到数组中然后使用双指针

1. 计算链表的长度
2. 创建等长的数组
3. 将链表中的数依次放入数组中
4. 使用左右指针判断链表是否是回文链表

时间复杂度：O(n)
空间复杂度：O(n)

思路2：快慢指针+反转链表

• 用快慢指针，快指针走两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置
• 同时用pre记录慢指针指向节点的前一个节点，用来分割链表
• 将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点
• 将后半部分翻转，得到cur2，前部分为cur1
• 按照cur1的长度，依次比较cur1和cur2的节点数值

方法一：对于思路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) {
        ListNode p = head;
        int length = 0;

        List<Integer> list = new ArrayList<>();
        int index = 0;

        // 计算链表的长度,并且将链表的值依次存入链表中
        while (p != null) {
            list.add(p.val);
            p = p.next;
            index ++;
        }

        // 使用左右指针,判断链表是否是回文链表
        int left = 0, right = list.size() - 1;
        for (;left <= right; left ++, right--) {
            if (list.get(left) != list.get(right)) {
                return false;
            }
        }
        return true;
    }
}

方法二：对应思路2

/**
 * 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) {
        // 1. 链表如果为空或者仅有一个节点，返回true
        if (head == null && head.next == null) return true;
        // 2. 定义快慢指针
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            // pre指针记录slow的前一个节点
            pre = slow;
            // fast指针一次走两步
            fast = fast.next.next;
            // slow指针一次走一步
            slow = slow.next;
        }
        // 分隔两个链表
        pre.next = null;
        // 前半部分
        ListNode cur1 = head;
        ListNode cur2 = reverseList(slow);

        while (cur1 != null) {
            if (cur1.val != cur2.val) return false;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }

    /**
        反转链表的代码
     */
    private ListNode reverseList(ListNode head) {
        ListNode curNode = head;
        ListNode preNode = null;
        ListNode nextNode;
        while (curNode != null) {
            nextNode = curNode.next;
            curNode.next =  preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}