力扣234. 回文链表

Problem: 234. 回文链表

题目描述

在这里插入图片描述在这里插入图片描述

思路

1.定义指针fast,slow分别指向head,int 类型变量n记录链表的长度;
2.将fast指针移动至 n 2 \frac{n}{2} 2n处;
3.若n为奇数则从fast -> next处反转链表;若为偶数则直接从fast位置翻转链表;
4.当fast不为空时,fast与slow每次向后走一步,若其指向的值不相同则返回false否则返回true

复杂度

时间复杂度:

O ( n ) O(n) O(n)

空间复杂度:

O ( 1 ) O(1) O(1)

Code

class Solution {
public:
    /**
     * Judge the palindromic linked list
     *
     * @param head The head node of linked list
     * @return bool
     */
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        ListNode* fast = head;
        ListNode* slow = head;
        int n = 0;
        while (p != nullptr) {
            n++;
            p = p -> next;
        }
        for (int i = 0; i < n / 2; ++i) {
            fast = fast -> next;
        }
        if (n % 2 == 0) {
            fast = reverse(fast);
        } else {
            fast = reverse(fast -> next);
        }
        while (fast != nullptr) {
            if (fast -> val != slow -> val) {
                return false;
            }
            fast = fast -> next;
            slow = slow -> next;
        }
        return true;
    }

    /**
     * Reverse the single linked list
     *
     * @param head The node to be reversed
     * @return ListNode*
     */
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nextP = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nextP;
        }
        return pre;
    }
};

相关推荐

  1. 234.

    2024-03-31 23:28:03       13 阅读
  2. 234.

    2024-03-31 23:28:03       3 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-03-31 23:28:03       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-03-31 23:28:03       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-03-31 23:28:03       8 阅读
  4. 高级IO——React服务器简单实现

    2024-03-31 23:28:03       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-03-31 23:28:03       7 阅读
  6. go第三方库go.uber.org介绍

    2024-03-31 23:28:03       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-03-31 23:28:03       9 阅读

热门阅读

  1. 关于 UnityEditorWindow

    2024-03-31 23:28:03       5 阅读
  2. 「PHP系列」PHP变量

    2024-03-31 23:28:03       6 阅读
  3. 计算机世界的“十六进制”为什么如此重要

    2024-03-31 23:28:03       5 阅读
  4. 蓝桥杯2014年第十三届省赛真题-切面条

    2024-03-31 23:28:03       5 阅读
  5. 【1单片机入门记录】DS18B20的应用

    2024-03-31 23:28:03       4 阅读
  6. C++中的类型转换

    2024-03-31 23:28:03       4 阅读
  7. C语言刷题(21)

    2024-03-31 23:28:03       5 阅读
  8. 算法刷题day37

    2024-03-31 23:28:03       4 阅读
  9. 优化代码分支

    2024-03-31 23:28:03       4 阅读
  10. c语言:把百分制转化为等级制度(switch语句)

    2024-03-31 23:28:03       6 阅读
  11. 搭建语音打电话机器人需要哪些技术和资源

    2024-03-31 23:28:03       5 阅读