LeetCode LCR 027. 回文链表

Categories:

题目描述
思路分析
1. 解法一：快慢指针 + 反转后半链表（推荐）
2. 解法二：栈辅助比较
相似题目

题目描述

✅ LCR 027. 回文链表

思路分析

解法一：快慢指针 + 反转后半链表（推荐）

核心思路：

用快慢指针找到链表中点，若长度为奇数，慢指针再前进一步跳过中点。

反转后半部分链表，与前半部分逐一比较。

只要出现不相等即可返回 false，否则为回文链表。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;

        // 快慢指针找中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        // 反转后半链表
        ListNode second = reverse(slow);
        ListNode p1 = head;
        ListNode p2 = second;

        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
}

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	slow, fast := head, head

	// 快慢指针找中点
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	if fast != nil {
		slow = slow.Next
	}

	// 反转后半链表
	second := reverseList(slow)
	p1, p2 := head, second

	for p2 != nil {
		if p1.Val != p2.Val {
			return false
		}
		p1 = p1.Next
		p2 = p2.Next
	}

	return true
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head

	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}

	return prev
}

解法二：栈辅助比较

核心思路：

用快慢指针遍历前半段，将节点值压入栈。

若长度为奇数，跳过中间节点。

继续遍历后半段，与栈顶依次对比。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(n)，使用栈保存前半段节点值。

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode slow = head;
        ListNode fast = head;

        // 压入前半段
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        // 对比后半段
        while (slow != null) {
            if (stack.isEmpty() || stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }

        return true;
    }
}

func isPalindrome(head *ListNode) bool {
	stack := make([]int, 0)
	slow, fast := head, head

	// 压入前半段
	for fast != nil && fast.Next != nil {
		stack = append(stack, slow.Val)
		slow = slow.Next
		fast = fast.Next.Next
	}

	if fast != nil {
		slow = slow.Next
	}

	// 对比后半段
	for slow != nil {
		n := len(stack)
		if n == 0 || stack[n-1] != slow.Val {
			return false
		}
		stack = stack[:n-1]
		slow = slow.Next
	}

	return true
}

相似题目

题目	难度	考察点
234. 回文链表	简单	链表 + 双指针
206. 反转链表	简单	链表
92. 反转链表 II	中等	链表
143. 重排链表	中等	链表
141. 环形链表	简单	快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/18931886