20/100 删除链表的倒数第 N 个结点 21/100 有效的括号 22/100 合并两个有序列表

20/100 删除链表的倒数第 N 个结点

题目：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

题解：

方法1：第一次完整遍历一遍得到长度，第二次遍历到倒数第n个数据前一个，进行删除

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = 0;
        ListNode* p = head;
        
        // 遍历一遍，得到链表长度
        while(p)
        {
            len++;
            p = p->next;
        }
        
        // 重新指向头节点
        p = head;
        ListNode* pre = nullptr;

        // 移动到倒数第N个节点的前一个节点
        for(int i = 1; i < len - n + 1; i++)
        {
            pre = p;
            p = p->next;
        }

        if (pre) {
           if (p) {//注意避免空指针问题
                pre->next = p->next;
                delete p;
            }
            return head;
        } else {
            // 如果pre为空，说明删除的是头节点
            ListNode* newHead = head->next;
            delete head;
            return newHead;
        }
    }
};

方法2： 双指针

双指针，第一个指针先往前走n， 再一起走，直到第一个指针走到最后一个， 此时第二个指针刚到要删除指针的前一个

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        // 将第一个指针先往前走n步
        for(int i = 0; i < n; i++)
        {
            if (fast) {
                fast = fast->next;
            } else {
                // 处理链表长度小于n的情况
                return head;
            }
        }
        
        // 一起移动两个指针，直到第一个指针走到最后一个
        while(fast && fast->next)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        // slow到要删除节点的前一个了
        if (slow && slow->next) {
            ListNode* x = slow->next;
            slow->next = slow->next->next;
            delete x;
            return head;
        } else {
            // 处理删除头节点的情况
            ListNode* newHead = head->next;
            delete head;
            return newHead;
        }
    }
};

注意：没有全部过case，应该是边界问题，有点困qiu，下把再试吧==

题目： 21/100 有效的括号

题解：

用栈 当出现左边的符号时入栈，如果出现了右边的符号，栈顶元素应该是对称的那个符号

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if(n %2 != 0) return false;
        stack<char> stk;
        unordered_map<char, char> pairs = {
            {')','('},
            {']','['},
            {'}','{'}};

        for(auto c : s)
        {
            if(c == '[' || c == '(' || c == '{')
            {
                stk.push(c);  
            }else
            {
                //是右边的符号
                // if(pairs[c] == stk.top() && !stk.empty())
                if(!stk.empty() && pairs[c] == stk.top())//应该先判空再判断是否相等
                {
                    stk.pop();
                }else{
                    //不配对
                    return false;
                }
            }
        }
        // return true;
        return stk.empty();

    }
};

题目： 22/100 合并两个有序列表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题解：

两个链表比较，把小的放到新链表中，第一次完全么有调试就一遍过了hhh，虽然是最暴力最简单的方式，但也有一点点开心。
但看了题解之后，发现人家的代码写的是真简介呀==

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        ListNode* dummy = new ListNode(0);
        ListNode* ptr = dummy;
        ListNode* p1 = list1;
        ListNode* p2 = list2;
        while (p1 && p2) {
            while (p1 && p2 && p1->val > p2->val) {
                ListNode* newNode = new ListNode(0);
                newNode->val = p2->val;
                ptr->next = newNode;
                ptr = ptr->next;

                p2 = p2->next;
            }

            while (p1 && p2 && p1->val <= p2->val) {
                ListNode* newNode = new ListNode(0);
                newNode->val = p1->val;
                ptr->next = newNode;
                ptr = ptr->next;

                p1 = p1->next;
            }
        }

        while (p1) {
            ListNode* newNode = new ListNode(0);
            newNode->val = p1->val;
            ptr->next = newNode;
            ptr = ptr->next;

            p1 = p1->next;
        }

        while (p2) {
            ListNode* newNode = new ListNode(0);
            newNode->val = p2->val;
            ptr->next = newNode;
            ptr = ptr->next;

            p2 = p2->next;
        }

        return dummy->next;
    }
};

//创建三个指针