LeetCode 刷题【19. 删除链表的倒数第 N 个结点、20. 有效的括号、21. 合并两个有序链表】

19. 删除链表的倒数第 N 个结点

自己做

解：多指针间隔处理

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode *k = head, *p = head, *q = head;
        
        //p、q间隔
        for(int i = 0; i < n; i++)
            q = q->next;
        
        //移动k、p、q
        while(q != nullptr){
            k = p;
            p = p->next;
            q = q->next;
        }

        //要删除头结点的情况单独处理
        if(k == p){
            head = head -> next;            //移动头结点的指向
        }

        //删除结点
        k-> next = p->next;
        delete(p);

        return head;
    }
};

20. 有效的括号

自己做

解：栈

class Solution {
public:

    bool isValid(string s) {
        int len = s.size();
        stack<char> p;

        for (int i = 0; i < len; i++) {
            
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')       //压栈
                p.push(s[i]);

            if(p.size() == 0)                       //栈为空，直接不匹配——> }、)、]开头
                return false;

            //出栈检查是否匹配，不匹配就返回false
            if (s[i] == ')') {
                if (p.top() != '(')
                    return false;
                //能匹配上就弹出栈
                p.pop();
            }
            if (s[i] == '}') {
                if (p.top() != '{')
                    return false;
                //能匹配上就弹出栈
                p.pop();
            }
            if (s[i] == ']') {
                if (p.top() != '[')
                    return false;
                //能匹配上就弹出栈
                p.pop();
            }
        }

        //栈清空，说明全部匹配
        if (p.size() == 0)
            return true;

        //栈不为空，说明有遗漏，不匹配
        return false;
    }
};

 21. 合并两个有序链表

自己做

解：归并

/**
 * 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) {
        ListNode *res = new ListNode();
        ListNode *p = list1, *q = list2, *k = res;
        
        while(p != nullptr && q != nullptr){
            if(p->val < q->val){    //p更小
                k->next = p;        //指向p
                p = p->next;        //p后移
            }
            else{                   //q更小
                k->next = q;        //指向q
                q = q->next;        //q后移
            }
            
            k = k->next;        //k后移
            k->next = nullptr;  //尾部置空
        }

        while(p != nullptr){        //list1还没有遍历完
            k->next = p;
            p = nullptr;
        }
        
        while(q != nullptr){        //list2还没有遍历完
            k->next = q;
            q = nullptr;
        }

        return res->next;
    }
};