leetcode234. 回文链表

发布时间:2024年01月16日

题目

给你一个单链表的头节点?head?,请你判断该链表是否为回文链表。如果是,返回?true?;否则,返回?false?。

示例 1:

输入:head = [1,2,2,1]
输出:true

示例 2:

输入:head = [1,2]
输出:false

提示:

  • 链表中节点数目在范围[1, 105]?内
  • 0 <= Node.val <= 9

?方法一

思路:

将链表转为数组,然后双指针判断即可。

代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vt; // 栈存放数组
        while(head){    // 链表 -> 栈
            vt.push_back(head->val);
            head = head->next;
        }
        // 定义双指针来对数组进行回文判断
        int left = 0, right = vt.size()-1;
        while(left < right){
            if(vt[left++] != vt[right--]){
                return false;
            }
        }
        return true;
    }
};

learn

这里因数组大小不好定义,所以可以使用 栈vector

方法二

反转链表,同时遍历,若不同,则返回false。

不知道为何这个方法总是返回false

 ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* next;
        while(cur){
            next = cur->next;   // cur的后面结点
            cur->next = prev;   // cur的前面结点
            prev = cur;
            cur = next;            
        }
        return prev;
    }
class Solution {    
public:
    bool isPalindrome(ListNode* head) {
        ListNode* reverse = reverseList(head);
        while(reverse && head){
            if(reverse->val != head->val){
                return false;
            }
            reverse = reverse->next;
            head = head->next;
        }
        return true;
    }
};

文章来源:https://blog.csdn.net/gsj9086/article/details/135617040
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。