力扣刷题随笔-526互联

力扣刷题随笔

回文链表

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

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

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

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

本题的思路就是利用双指针的方法来比较但是由于是单链表所以没有办法从后往前找所以我们必须先将数据存到数组里面这样我们才可以从后往前找从前往后找

vector<int> vals;
        while(head!=nullptr){
            vals.push_back(head->val);
            head=head->next;
        }

然后再用双指针法来判断是否是回文数

for(int i=0,j=(int)vals.size()-1;i<j;i++,j--){
            if(vals[i] != vals[j]){
                return false;
            }
        }

下面是完整代码

/**
 * 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) {
        vector<int> vals;
        while(head!=nullptr){
            vals.emplace_back(head->val);
            head=head->next;
        }
        for(int i=0,j=(int)vals.size()-1;i<j;i++,j--){
            if(vals[i] != vals[j]){
                return false;
            }
        }
        return true;

    }
};

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

第一种思路就是让一个cur指针指向当前的节点判断当前节点的下一个节点是否需要删除如果需要删除就让当前节点的next指向下一个节点的下一个节点也就是cur->nest=cur->next->next

完整代码如下：

/**
 * 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:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* xuni = new ListNode(0);
        xuni->next = head;
        ListNode* cur = xuni;
        while(cur->next){
            if(cur->next->val == val){
                cur->next = cur->next->next;
            }
            else{
                cur=cur->next;
            }

        }
        return xuni->next;

    }
};

第二种思路就是递归这个是参考官方给的题解判断当前节点的下一个节点是否需要删除和上面思路其实是一样的。

/**
 * 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:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr){
            return head;
        }
        head->next = removeElements(head->next,val);

        return head->val == val?head->next:head;


    }
};

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

提示：

-231 <= n <= 231 - 1

思路就是负数不是 1 是奇数不是判断一个数是否是2的幂可以判断他除2之后是不是2 的幂

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0){
            return false;
        }
        if(n == 1){
            return true;
        }
        if(n%2==1){
            return false;
        }

        return isPowerOfTwo(n/2);
    }
};