3274. 检查棋盘方格颜色是否相同
class Solution {
public:
bool checkTwoChessboards(string coordinate1, string coordinate2) {
int x1 = coordinate1[0] - 'a';
int y1 = coordinate1[1] - '0';
int x2 = coordinate2[0] - 'a';
int y2 = coordinate2[1] - '0';
return ((x1 + y1) % 2) == ((x2 + y2) % 2);
}
};
234. 回文链表
/**
* 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) {
int n = 0;
ListNode* temp = head;
while(temp != nullptr){
temp = temp->next;
n++;
}
int t = n / 2;
ListNode* pre = nullptr;
ListNode* cur = head;
while (t--) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
if(n % 2 != 0) cur = cur->next;
while(pre != nullptr && cur != nullptr){
if(pre->val != cur->val) return false;
pre = pre->next;
cur = cur->next;
}
return true;
}
};
141. 环形链表
/**
* 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* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
142. 环形链表 II
/**
* 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) {
unordered_set<ListNode *> mp;
while (head != nullptr) {
if (mp.count(head)) {
return head;
}
mp.insert(head);
head = head->next;
}
return nullptr;
}
};
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* ans = nullptr;
ListNode* before;
if(list1 == nullptr && list2 != nullptr) return list2;
if(list1 != nullptr && list2 == nullptr) return list1;
while(list1 != nullptr && list2 != nullptr){
if(list1->val > list2->val){
if(ans == nullptr) ans = list2;
while(list2->next != nullptr && list2->next->val <= list1->val) list2 = list2->next;
before = list2;
list2 = list2->next;
before->next = list1;
} else {
if(ans == nullptr) ans = list1;
while(list1->next != nullptr && list1->next->val <= list2->val) list1 = list1->next;
before = list1;
list1 = list1->next;
before->next = list2;
}
}
if(list1 == nullptr && list2 != nullptr){
}
return ans;
}
};
2. 两数相加
/**
* 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) {
int add = 0, c1 = 0, c2 = 0;
ListNode* ans1 = l1;
ListNode* ans2 = l2;
ListNode* last1;
ListNode* last2;
while(l1 != nullptr || l2 != nullptr){
int l1_val = l1 == nullptr ? 0 : l1->val;
int l2_val = l2 == nullptr ? 0 : l2->val;
int sum = (l1_val + l2_val + add);
if(l1 != nullptr) l1->val = sum % 10;
if(l2 != nullptr) l2->val = sum % 10;
add = sum / 10;
if(l1 != nullptr){
last1 = l1;
l1 = l1->next;
c1++;
}
if(l2 != nullptr){
last2 = l2;
l2 = l2->next;
c2++;
}
}
if(add){
if(c1 < c2){
last2->next = last1;
last1->val = add;
} else {
last1->next = last2;
last2->val = add;
}
}
return c1 < c2 ? ans2 : ans1;
}
};
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) {
int ct = 0;
ListNode* p = head;
while(p != nullptr){
p = p->next;
ct++;
}
if(n == ct){
head = head->next;
return head;
};
p = head;
n = ct - n - 1;
while(n--){
p = p->next;
}
p->next = p->next->next;
return head;
}
};
24. 两两交换链表中的节点
/**
* 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* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* p = head;
ListNode* nnx;
head = head->next;
while(p != nullptr && p->next != nullptr){
ListNode* jump = p->next->next;
if(p->next->next != nullptr){
nnx = p->next->next->next;
} else {
nnx = nullptr;
}
p->next->next = p;
if(nnx == nullptr){
p->next = jump;
} else {
p->next = nnx;
}
p = jump;
}
return head;
}
};
