LeetCode-Day9-C++
搜索二维矩阵II
编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。题目链接
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20输出：false
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int startrow = 0, startcol = matrix[0].size() - 1; while(startrow < matrix.size() && startcol >= 0){ if(matrix[startrow][startcol] > target){ startcol--; } else if(matrix[startrow][startcol] < target){ startrow++; } else{ return true; } } return false; } };反转链表
给你单链表的头节点head，请你反转链表，并返回反转后的链表。题目链接
示例 1：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]输出：[2,1]
示例 3：
输入：head = []输出：[]
/** * 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 = NULL; ListNode* last = head; if(!head){ return head; } while(last != NULL){ ListNode* temp = last->next; last->next = pre; pre = last; last = temp; } return pre; } };回文链表
给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。题目链接
示例 1：
输入：head = [1,2,2,1]输出：true
示例 2：
输入：head = [1,2]输出：false
/** * 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) { ListNode* slow = head; ListNode* fast = head->next; //先把链表一份为二 while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } //反转后半段链表 ListNode* second = reverselist(slow->next); slow->next = NULL; //比较两部分链表 ListNode* first = head; while(second){ if(first->val != second->val){ return false; } first = first->next; second = second->next; } return true; } ListNode* reverselist(ListNode* head){ ListNode* pre = NULL; ListNode* last = head; if(!head){ return head; } while(last){ ListNode* temp = last->next; last->next = pre; pre = last; last = temp; } return pre; } };