LeetCode每日一题-3：回文链表

墨明棋妙27

发布于 2022-09-23 11:27:43

2750

文章被收录于专栏：19961996

题目描述：

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

示例 1:

输入: 1->2输出: false

示例 2:

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

思路分析：

迭代法：

避免使用 O(n)O(n) 额外空间的方法就是改变输入。

我们可以将链表的前（后）半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。

该方法虽然可以将空间复杂度降到 O(1)O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

整个流程可以分为以下步骤：

找到前（后）半部分链表的尾节点。反转（前）后半部分链表。判断是否回文。

Python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        fast = slow = q = head
        while fast.next and fast.next.next:#这里快指针的判读条件跟判断环形有一点不同
            fast = fast.next.next
            slow = slow.next
        def reverse_list(head):
            if head is None:
                return head
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            return cur
        p = reverse_list(slow.next)
        while p.next:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return p.val == q.val

java实现：

/**
 * 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 || head.next == null) {
            return true;
        }
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=null,prepre=null;
       //反转前半部分指针
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
            pre.next=prepre;
            prepre=pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
       //比较前后部分指针是否相同
        while(pre!=null&&slow!=null){
            if(pre.val!=slow.val){
                return false;
            }
            pre=pre.next;
            slow=slow.next;
        }
        return true; 
    }
}

递归法：

currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

算法的正确性在于递归处理节点的顺序是相反的，而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。

所谓递归，即从上往下递下去，然后再从下往上归回来。

java实现代码：

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-28，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

本文分享自计算机视觉CV 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

java

登录后参与评论

0 条评论

热度