一.矩阵

1.旋转图像

旋转图像
观察规律可得：
matrix[i][j] 最终会被交换到 matrix [j][n−i−1]位置，最初思路是直接上三角交换，但是会存在问题，有几个元素是无法交换到的

错误示范

    void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for (int i = 0 ; i < n; i++) {for (int j = 0; j < i; j++) {swap(matrix[i][j], matrix[j][n - i - 1]);}}} }; ```解答错误 执行用时: 0 ms Case 1 输入 matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出               [[7,4,3],[8,5,6],[1,2,9]] 预期结果        [[7,4,1],[8,5,2],[9,6,3]]

看了解题思路，需要水平翻转 + 主对角线翻转
水平翻转：

主对角线翻转：

对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即
matrix[i][j] ==> matrix[n - i - 1][j]
对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，即
matrix[i][j] ==> matrix[j][i]
联立可得：
matrix[i][j] ==> matrix[j][n - i - 1]

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for (int i = 0 ; i < n / 2; i++) {for (int j = 0; j < n; j++) {swap(matrix[i][j], matrix[n - i - 1][j]);}}for (int i = 0 ; i < n ; i++) {for (int j = 0; j < i; j++) {swap(matrix[i][j], matrix[j][i]);}}}
};

二.链表

1. 相交链表

相交链表
当链表 headA和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

• 每步操作需要同时更新指针 pA 和 pB。
• 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
• 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
• 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) {return nullptr;}ListNode *pa = headA, *pb = headB;while (pa != pb) {pa = pa == nullptr ? headB : pa->next;pb = pb == nullptr ? headA : pb->next;}return pa;}
};

2.反转链表

反转链表
假设链表为 1→2→3→∅1，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

1.保存后继节点 tmp = cur->next
2.让当前节点指向pre节点 cur->next = pre
3.暂存当前节点，这是后继节点需要指向的pre, pre = cur
4.访问下一个节点 cur = tmp

pre最终保存的是头节点

/*** 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* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* cur = head;while(cur != nullptr) { ListNode* nextnode = cur->next;cur->next = pre;pre = cur;cur = nextnode;}return pre;}
};

3.回文链表

回文链表
存数组中进行比较，但是空间复杂度为o(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:bool isPalindrome(ListNode* head) {vector<int> ans;while(head != nullptr) {ans.push_back(head->val);head = head->next;}int n = ans.size();for (int i = 0, j = n - 1; i < j; i++, j--) {if (ans[i] != ans[j]) return false;}return true;}
};

4.环形链表

环形链表
龟兔赛跑，乌龟走一步，兔子走两步，如果有环总能相遇
需要注意的是：while的条件是fast & fast->next不为空

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if (head == nullptr || head->next == nullptr) return false;ListNode *fast = head, *slow = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) return true;}return false;}
};

5.环形链表 II

环形链表 II
基于上一题环形链表，如果slow和fast相遇，让其中一个指针重新指向head，并且两个指针都每次只走一步，再次相遇就是环的入口

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if (head == nullptr || head->next == nullptr) return nullptr;ListNode *slow = head, *fast = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;if (slow == fast) {fast = head;while (fast != slow) {slow = slow->next;fast = fast->next;}return fast;}}return nullptr;}
};