LeetCode 234. 回文链表

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 234. 回文链表

思路分析

使用快慢指针找到链表的中点。

将链表从中点分成两部分，并反转后半部分链表。

依次比较前半部分和反转后的后半部分链表的节点值，如果所有节点值都相等，则链表是回文链表。

参考代码

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
	}

	// 反转后半部分链表
	pre, cur := slow, slow.Next
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	slow.Next = nil

	// 比较前后两部分链表
	p1, p2 := head, pre
	for p2 != nil {
		if p1.Val != p2.Val {
			return false
		}
		p1 = p1.Next
		p2 = p2.Next
	}
	return true
}

时间复杂度：O (n)，其中 n 是链表的长度。找到中点、反转链表和比较链表都需要线性时间。

空间复杂度：O (1)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode pre = null, cur = slow;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        ListNode p1 = head, p2 = pre;
        while (p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/54516872