两数相加
两个非空的链表，表示两个非负的整数。它们每位数字都按照逆序的方式存储的，并且每个节点只能存储一位数字。
模拟
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = nullptr, *curr = nullptr;
int carry = 0;
while(l1 || l2){
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
if(!head){
head = curr = new ListNode(sum%10);
}else{
curr->next = new ListNode(sum%10);
curr = curr->next;
}
carry = sum/10;
if(l1){
l1 = l1->next;
}
if(l2){
l2 = l2->next;
}
}
if(carry > 0){
curr->next = new ListNode(carry);
}
return head;
}
};
删除链表的倒数第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* p = head;
int size = 0;
while(p){
size++;
p = p->next;
}
if(size == n){
head = head->next;
}
int num = size - n;
p = head;
while(num){
if(num == 1){
p->next = p->next->next;
break;
}
num--;
p = p->next;
}
return head;
}
};
两两交换链表中的节点
只能进行节点交换
递归
递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。
如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。
用head表示原始链表的头节点，新的链表的第二个节点，newHead为新的链表的头节点。
class Solution{
public:
ListNode* swapPairs(ListNode *head){
if(head == nullptr || head->next == nullptr){
return head;
}
ListNode *newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
}
随机链表的复制
给一个长度为n的链表，每个结点包含一个额外增加的随机数指针random，该指针可以指向链表中的任何节点或空节点。
回溯+哈希表
如果是普通链表，可以直接按照遍历的顺序创建链表节点。
因为随机指针的存在，当我们拷贝结点时，当前节点的随机指针指向的节点可能还没创建。
利用回溯的方式，让每个节点的拷贝操作相互独立。
对于当前节点，我们首先要进行拷贝，然后进行当前节点的前节点和后节点拷贝，拷贝完成后将创建的新节点的指针返回。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> cacheNode;
Node* copyRandomList(Node* head) {
if(head == nullptr){
return nullptr;
}
if(!cacheNode.count(head)){
Node* headNew = new Node(head->val);
cacheNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cacheNode[head];
}
};
颜色分类
红、白、蓝进行原地排序，使得相同颜色的元素相邻。
单指针
对数组进行两次遍历。第一次遍历中，将所有0交换到数组头部，第二次遍历，将所有1交换到0之后。
class Solution {
public:
void sortColors(vector<int>& nums) {
int index = 0;
for(int i=index; i<nums.size(); i++){
if(nums[i] == 0){
swap(nums[i],nums[index]);
index++;
}
}
for(int i=index; i<nums.size(); i++){
if(nums[i] == 1){
swap(nums[i],nums[index]);
index++;
}
}
}
};
二叉树的中序遍历
二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树。
这个过程天然具有递归的性质，可以直接用递归函数来模拟这一过程。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res){
if(!root){
return;
}
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
};
迭代
递归的方式也可以用迭代实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来。
翻转二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root){
return root;
}
TreeNode* left = invertTree(root->left);
TreeNode*right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
对称二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool check(TreeNode* p, TreeNode* q){
if(!p && !q){
return true;
}
if(!p || !q){
return false;
}
return (p->val == q->val) && check(p->left,q->right) && check(p->right,q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};
