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、qwhile(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;//出栈检查是否匹配，不匹配就返回falseif (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; //指向pp = p->next; //p后移}else{ //q更小k->next = q; //指向qq = 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;}
};
