回文链表( LeetCode 234 )

一、题目描述

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 回文链表( LeetCode 234 ): https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution {
    public boolean isPalindrome(ListNode head) {

        // 边界情况判断

        // 链表为空或者只有一个节点的情况,属于回文链表
        if(head == null || head.next == null) return true;

        // 链表只有两个节点的时候,判断这两个节点值是否相等
        if(head.next.next == null) return head.val == head.next.val;

        // 通过快慢指针寻找链表的中心点

        // 设置一个指针,指向链表的头部
        // fast 这个指针每次都向后移动两步
        ListNode fast = head;


        // 设置一个指针,指向链表的头部
        // slow 这个指针每次都向后移动一步
        ListNode slow = head;

        // 让 fast 和 slow 同时向后移动
        // 其中,fast 这个指针每次都向后移动两步,slow 这个指针每次都向后移动一步
        // 直到 fast 这个指针指向了链表的尾节点,即 fast.next = null
        // 或者 fast 这个指针指向了链表的尾节点的前一个节点,即 fast.next.next = null
        // 这个时候,fast 这个指针无法向后移动两位,跳出循环,找到了中间点
        // 如果链表长度为偶数,则 slow 指向了中间节点前的那个节点
        // 比如链表为  1 --> 2 --> 3 --> 4 --> null

        // 一开始,slow 和 fast 同时指向 1,slow 移动一位到 2,fast 移动两位到 3
        // 由于 3.next.next 为空,所以跳出 while,此时 slow 指向了中间节点前的那个节点

        // 如果链表长度为奇数,则 slow 指向了中间节点
        // 比如链表为  1 --> 2 --> 3 
        // 一开始,slow 和 fast 同时指向 1,slow 移动一位到 2,fast 移动两位到 3
        // 由于 3.next 为空,所以跳出 while,此时 slow 指向了中间节点

        while(fast.next != null && fast.next.next != null){
            // slow 这个指针每次都向后移动一步
            slow = slow.next;
            // fast 这个指针每次都向后移动两步
            fast = fast.next.next;
        }

        // 这个时候,slow 指向的那个节点把链表划分为两个区域
        // 翻转右区域的链表
        // 获取右区域的链表翻转之后的头节点
        ListNode rightHead =  reverse(slow.next);

        // 获取左区域的链表的头节点
        ListNode leftHead = head;

        // 让 leftHead 和 rightHead 同时向后移动,直到 rightHead 指向 null 为止
        // 说明比较完了所有的节点
        while(rightHead != null){
            // 如果它们的节点值不一样,那么就不是回文链表
            if(leftHead.val != rightHead.val){
                // 不是回文链表,返回 false
                return false;
            }
            // 否则,让 rightHead 继续向右移动
            rightHead = rightHead.next;

            // 否则,让 rightHead 继续向右移动
            leftHead = leftHead.next;

        }

        // 比较完所有的节点,说明是回文链表,返回 true
        return true;

    }

    // 反转链表的代码
    private ListNode reverse(ListNode head) {
        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下,反转之后的结果还是它自己本身
        if( head == null || head.next == null)  return head;

        // 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        ListNode cur = reverse(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        // 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        // 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;

        // head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 回文链表( LeetCode 234 ): https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 边界情况判断

        // 链表为空或者只有一个节点的情况,属于回文链表
        if(head == NULL || head->next == NULL) return true;

        // 链表只有两个节点的时候,判断这两个节点值是否相等
        if(head->next->next == NULL) return head->val == head->next->val;

        // 通过快慢指针寻找链表的中心点

        // 设置一个指针,指向链表的头部
        // fast 这个指针每次都向后移动两步
        ListNode* fast = head;


        // 设置一个指针,指向链表的头部
        // slow 这个指针每次都向后移动一步
        ListNode* slow = head;

        // 让 fast 和 slow 同时向后移动
        // 其中,fast 这个指针每次都向后移动两步,slow 这个指针每次都向后移动一步
        // 直到 fast 这个指针指向了链表的尾节点,即 fast->next = NULL
        // 或者 fast 这个指针指向了链表的尾节点的前一个节点,即 fast->next->next = NULL
        // 这个时候,fast 这个指针无法向后移动两位,跳出循环,找到了中间点
        // 如果链表长度为偶数,则 slow 指向了中间节点前的那个节点
        // 比如链表为  1 --> 2 --> 3 --> 4 --> NULL

        // 一开始,slow 和 fast 同时指向 1,slow 移动一位到 2,fast 移动两位到 3
        // 由于 3->next->next 为空,所以跳出 while,此时 slow 指向了中间节点前的那个节点

        // 如果链表长度为奇数,则 slow 指向了中间节点
        // 比如链表为  1 --> 2 --> 3 
        // 一开始,slow 和 fast 同时指向 1,slow 移动一位到 2,fast 移动两位到 3
        // 由于 3->next 为空,所以跳出 while,此时 slow 指向了中间节点

        while(fast->next != NULL && fast->next->next != NULL){
            // slow 这个指针每次都向后移动一步
            slow = slow->next;
            // fast 这个指针每次都向后移动两步
            fast = fast->next->next;
        }

        // 这个时候,slow 指向的那个节点把链表划分为两个区域
        // 翻转右区域的链表
        // 获取右区域的链表翻转之后的头节点
        ListNode* rightHead =  reverse(slow->next);

        // 获取左区域的链表的头节点
        ListNode* leftHead = head;

        // 让 leftHead 和 rightHead 同时向后移动,直到 rightHead 指向 NULL 为止
        // 说明比较完了所有的节点
        while(rightHead != NULL){
            // 如果它们的节点值不一样,那么就不是回文链表
            if(leftHead->val != rightHead->val){
                // 不是回文链表,返回 false
                return false;
            }
            // 否则,让 rightHead 继续向右移动
            rightHead = rightHead->next;

            // 否则,让 rightHead 继续向右移动
            leftHead = leftHead->next;

        }

        // 比较完所有的节点,说明是回文链表,返回 true
        return true;

    }
// 反转链表的代码
private:
    ListNode* reverse(ListNode* head) {
        // 寻找递归终止条件
        // 1、head 指向的结点为 NULL 
        // 2、head 指向的结点的下一个结点为 NULL 
        // 在这两种情况下,反转之后的结果还是它自己本身
        if( head == NULL || head->next == NULL)  return head;

        // 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        ListNode* cur = reverse(head->next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候,head 为 4,那么 head->next = 5
        // 那么 head->next->next 就是 5->next ,意思就是去设置 5 的下一个节点
        // 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head->next->next = head;


        // head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head->next = NULL;

        // 我们把每次反转后的结果传递给上一层
        return cur;
 }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 回文链表( LeetCode 234 ): https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 边界情况判断

        # 链表为空或者只有一个节点的情况,属于回文链表
        if head == None or head.next == None :
           return True

        # 链表只有两个节点的时候,判断这两个节点值是否相等
        if head.next.next == None :
           return head.val == head.next.val

        # 通过快慢指针寻找链表的中心点

        # 设置一个指针,指向链表的头部
        # fast 这个指针每次都向后移动两步
        fast = head


        # 设置一个指针,指向链表的头部
        # slow 这个指针每次都向后移动一步
        slow = head

        # 让 fast 和 slow 同时向后移动
        # 其中,fast 这个指针每次都向后移动两步,slow 这个指针每次都向后移动一步
        # 直到 fast 这个指针指向了链表的尾节点,即 fast.next = None
        # 或者 fast 这个指针指向了链表的尾节点的前一个节点,即 fast.next.next = None
        # 这个时候,fast 这个指针无法向后移动两位,跳出循环,找到了中间点
        # 如果链表长度为偶数,则 slow 指向了中间节点前的那个节点
        # 比如链表为  1 --> 2 --> 3 --> 4 --> None

        # 一开始,slow 和 fast 同时指向 1,slow 移动一位到 2,fast 移动两位到 3
        # 由于 3.next.next 为空,所以跳出 while,此时 slow 指向了中间节点前的那个节点

        # 如果链表长度为奇数,则 slow 指向了中间节点
        # 比如链表为  1 --> 2 --> 3 
        # 一开始,slow 和 fast 同时指向 1,slow 移动一位到 2,fast 移动两位到 3
        # 由于 3.next 为空,所以跳出 while,此时 slow 指向了中间节点

        while fast.next != None and fast.next.next != None :
            # slow 这个指针每次都向后移动一步
            slow = slow.next
            # fast 这个指针每次都向后移动两步
            fast = fast.next.next


        # 这个时候,slow 指向的那个节点把链表划分为两个区域
        # 翻转右区域的链表
        # 获取右区域的链表翻转之后的头节点
        rightHead =  self.reverseList(slow.next)

        # 获取左区域的链表的头节点
        leftHead = head

        # 让 leftHead 和 rightHead 同时向后移动,直到 rightHead 指向 None 为止
        # 说明比较完了所有的节点
        while rightHead != None :
            # 如果它们的节点值不一样,那么就不是回文链表
            if leftHead.val != rightHead.val :
                # 不是回文链表,返回 False
                return False

            # 否则,让 rightHead 继续向右移动
            rightHead = rightHead.next

            # 否则,让 rightHead 继续向右移动
            leftHead = leftHead.next


        # 比较完所有的节点,说明是回文链表,返回 true
        return True


    # 反转链表的代码
    def reverseList(self,head:ListNode) -> ListNode:
        # 寻找递归终止条件
        # 1、head 指向的结点为 None 
        # 2、head 指向的结点的下一个结点为 None 
        # 在这两种情况下,反转之后的结果还是它自己本身
        if head == None or head.next == None:
           return head

        # 不断的通过递归调用,直到无法递归下去,递归的最小粒度是在最后一个节点
        # 因为到最后一个节点的时候,由于当前节点 head 的 next 节点是空,所以会直接返回 head
        cur = self.reverseList(head.next)


        # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        # 第一次执行下面代码的时候,head 为 4,那么 head.next = 5
        # 那么 head.next.next 就是 5.next ,意思就是去设置 5 的下一个节点
        # 等号右侧为 head,意思就是设置 5 的下一个节点是 4

        # 这里出现了两个 next
        # 第一个 next 是「获取」 head 的下一节点
        # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head


        # head 原来的下一节点指向自己,所以 head 自己本身就不能再指向原来的下一节点了
        # 否则会发生无限循环
        head.next = None

        # 我们把每次反转后的结果传递给上一层
        return cur

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注