带你粗略了解C++回文链表

目录
  • 请判断一个链表是否为回文链表。
  • 思路
  • 总结

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

思路

1.用快慢指针，快指针有两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置

2.同时用pre记录慢指针指向节点的前一个节点，用来分割链表

3.将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点

4.将后半部分反转 ，得cur2，前半部分为cur1

5.按照cur1的长度，一次比较cur1和cur2的节点数值

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return true;
        ListNode* fast=head; //快指针
        ListNode* slow=head; //慢指针，找到链表的中间位置
        ListNode* pre=head;  //慢指针的前一个指针，用来分割链表
        while(fast&&fast->next){  //循环条件是fast和fast的下一个节点是否都存在，不用写fast!=nullptr&&fast->next!=nullptr，直接fast&&fast->next
            pre=slow;
            fast=fast->next->next;
            slow=slow->next;
            //per=slow; //这句不能放在这，这里的slow是slow->next。只能放在slow=slow->next的前面。
        }
        pre->next=nullptr;  //分割链表。per是前半部分链表的最后一个节点，所以是per的下一个结点为空，不是per==nullptr
        ListNode* cur1=head; //前半部分的链表
        ListNode* cur2=reverse(slow);  //对后半部分的链表进行反转,reverse(ListNode* slow)错误，调用不用写类型ListNode*

        while(cur1){ //循环条件是cur是否为空
            if(cur1->val!=cur2->val)  // 若有一个不相等则返回false
                return false;
            cur1=cur1->next;   //  判断下一个节点
            cur2=cur2->next;   //
        }
        return true;  //都等于则true
    }
        //反转链表
        ListNode* reverse(ListNode* head){
            ListNode* temp; //保存cur的下一个节点,下一次要操作cur->next的节点
            ListNode* cur=head;
            ListNode* pre=nullptr;
            while(cur){
                temp=cur->next;
                cur->next=pre;
                pre=cur;
                cur=temp;
            }
            return pre;
        }
};

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 常见排序方法有

  • C++数据结构之链表详解

    C++数据结构之链表详解

    目录 前言 一.删除链表中给定值为key的节点 二.反转链表 三.返回链表的中间节点 四.删除链表的倒数第K个节点 五.分割链表 六.合并两个有序链表 七.删除有序链表中重复节点 八.环形链表 九.相交链表 十.两数相加 十一.回文链表 总结 前言 链表类型的习题常用的技巧就是定义指针来代替head的,替head走,要么就是数学问题,环形链表就是利用数学思想取解决的,要么就是定义双指针来操作链表. 一.删除链表中给定值为key的节点 定义两个变量,一个使待删除的节点,一个为待删除节点的前驱节点,

  • C++实现LeetCode(160.求两个链表的交点)

    [LeetCode] 160.Intersection of Two Linked Lists 求两个链表的交点 Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:          a1 → a2 c1 → c2 → c3             B:     b1

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • 带你粗略了解C++回文链表

    带你粗略了解C++回文链表

    目录 请判断一个链表是否为回文链表. 思路 总结 请判断一个链表是否为回文链表. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 思路 1.用快慢指针,快指针有两步,慢指针走一步,快指针遇到终止位置时,慢指针就在链表中间位置 2.同时用pre记录慢指针指向节点的前一个节点,用来分割链表 3.将链表分为前后均等两部分,如果链表长度是奇数,那么后半部分多一个节点 4.将后半部分反转 ,得cur2,前半部分为cur1 5.按照

  • Python3实现的判断回文链表算法示例

    本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置

  • Python判断回文链表的方法

    Python判断回文链表的方法

    什么是回文数? 回文数简单的说就是正着倒着读都是一样的,比如:12321,1221,1111等等,正着读也是12321,倒着读也是12321. 首先,接收用户输入数字列表转换成链表 比如用户输入:1 2 3 2 1,转换为链表后,如下图 首先接收用户输入数字列表,每个数字用空格分隔,使用split截断字符串,使用map,把每个元素映射成int类型,然后再转成list,使用循环取出每项元素添加到链表中. lt = list(map(int, s.split(' '))) 代码如下: # 链表类 c

  • 用JAVA实现单链表，检测字符串是否是回文串

    一.需求 使用JAVA实现单链表,使用单链表检测字符串是否是回文串 二.需求分析 回文串最重要的就是对称,那么最重要的问题就是找到那个中心,用快指针每步走两格,当他到达链表末端的时候,慢指针刚好到达中心,慢指针在遍历过程中(快指针到达末端时)把走过的节点进行反向操作,此时从中位点分为前后两部分,此时前半部分的指针开始往回指(取next的时候,取的是前一个节点),而慢指针继续向前,跟前半部分的数据依次进行比对,当慢指针扫完整个链表,就可以判断这是回文串,否则就提前退出,同时在前半部分往回遍历的过程

  • Python实现常见的回文字符串算法

    回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]

  • java中利用栈实现字符串回文算法

    问题 给定一个由多个a和b组成的字符串数组,字符串中有一个特殊的字符X,位于字符串的正中间,例如(aaaabbbbXabaabbbb),如何判定该字符串是否回文 简单算法 定义两个下标分别指向字符串的头和尾,每次比较两个下标位置的值是否相等,如果不相等,那么输入的 字符串不是回文,如果相等,左边的下表加1,右边的下表减1,重复上述步骤直至两个下标都指向字符串的正中间或者确定字符串不是回文 /** * 判断字符串是否是回文 */ public int isPalindrome(String inp

  • C++实现LeetCode(131.拆分回文串)

    [LeetCode] 131.Palindrome Partitioning 拆分回文串 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"

  • C++实现LeetCode(验证回文字符串)

    [LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a

  • 如何利用JS判断整数x是否是回文数

    目录 题目 解题思路 代码实现 其他方法 总结 题目 给你一个整数 x ,如果 x 是一个回文整数,返回 true :否则,返回 false . 回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数.例如,121 是回文,而 123 不是. 示例 1: 输入:x = 121 输出:true 示例 2: 输入:x = -121 输出:false 解释:从左向右读, 为 -121 . 从右向左读, 为 121- .因此它不是一个回文数. 示例 3: 输入:x = 10 输出:false 解释

  • C++实现LeetCode(125.验证回文字符串)

    [LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a

随机推荐