234. 回文链表

题目描述

给定一个单链表的头节点 head，判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。

---

示例

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

---

解题思路

判断链表是否为回文的关键在于：

1. 找到链表的中点。
2. 反转链表的后半部分。
3. 比较前半部分和后半部分是否相同。

1. 找到链表的中点

使用快慢指针方法：

• 快指针每次走两步，慢指针每次走一步。当快指针到达链表末尾时，慢指针刚好到达链表的中点。

2. 反转链表的后半部分

将链表的后半部分原地反转，从而可以直接比较前半部分和后半部分是否相同。

3. 比较两部分

从链表头部和反转后的中点分别开始遍历，逐一比较节点值。如果所有值都相同，则链表是回文。

注意事项

• 需要恢复链表的原始结构（如果面试中有要求）。
• 空链表或只有一个节点的链表都是回文。

---

代码实现

方法：快慢指针 + 链表反转

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取链表节点值
        String[] values = scanner.nextLine().split(" ");
        ListNode head = null;
        ListNode tail = null;
        for (String val : values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (head == null) {
                    head = newNode;
                    tail = newNode;
                } else {
                    tail.next = newNode;
                    tail = newNode;
                }
            }
        }

        Solution solution = new Solution();
        boolean result = solution.isPalindrome(head);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; // 空链表或只有一个节点，必定是回文
        }

        // 1. 找到链表的中点（快慢指针）
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; // 慢指针走一步
            fast = fast.next.next; // 快指针走两步
        }

        // 2. 反转后半部分链表
        ListNode secondHalf = reverseList(slow);

        // 保存反转后的链表头，用于后续恢复链表（如果需要）
        ListNode secondHalfCopy = secondHalf;

        // 3. 比较前半部分和后半部分
        ListNode firstHalf = head;
        boolean isPalindrome = true;
        while (secondHalf != null) { // 只需遍历后半部分
            if (firstHalf.val != secondHalf.val) {
                isPalindrome = false;
                break;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        // 4. 恢复链表的原始结构（可选）
        reverseList(secondHalfCopy);

        return isPalindrome;
    }

    // 辅助函数：反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode nextTemp = head.next;
            head.next = prev;
            prev = head;
            head = nextTemp;
        }
        return prev;
    }
}

// 链表节点定义
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

---

代码详解

1. 快慢指针找到链表中点：

   • 快指针每次走两步，慢指针每次走一步。
   • 快指针到达末尾时，慢指针到达链表中点。

2. 反转后半部分链表：

   • 使用辅助函数 reverseList，将后半部分链表反转。
   • 时间复杂度为 (O(n/2))。

3. 比较前半部分和后半部分：

   • 遍历反转后的后半部分，逐一比较值是否相同。

4. 恢复链表（可选）：

   • 如果题目要求链表保持原始结构，可再次反转后半部分链表。

---

测试用例

1. 普通回文链表：

   • 输入：head = [1,2,2,1]
   • 输出：true

2. 非回文链表：

   • 输入：head = [1,2]
   • 输出：false

3. 空链表：

   • 输入：head = []
   • 输出：true

4. 单节点链表：

   • 输入：head = [1]
   • 输出：true

5. 长回文链表：

   • 输入：head = [1,2,3,2,1]
   • 输出：true

---

时间和空间复杂度

1. 时间复杂度：

   • 找到中点：(O(n))。
   • 反转链表：(O(n/2))。
   • 比较两部分：(O(n/2))。
   • 总时间复杂度：(O(n))。

2. 空间复杂度：

   • 反转链表使用了常数级别的额外指针，空间复杂度为 (O(1))。

---