24. 两两交换链表中的节点 - 力扣（LeetCode）
思路:这道题一定要把握好交换的顺序，否则很容易成环导致无法出循环
我的AC代码
//时间复杂度O(n),空间复杂度O(1)
/**
* 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* dummyHead = new ListNode(-1,head);
ListNode* cur = dummyHead;
while(cur != nullptr && cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next->next;
cur->next->next = tmp->next;
tmp->next = cur->next;
cur->next = tmp;
cur = cur->next->next;
}
return dummyHead->next;
}
};我的答案和标准答案顺序上不太一样，但运行起来效果差不多，所以这题不是只有一种特定的顺序，只要逻辑通就可以
标准答案
//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
思路:我的思路是先算出整个链表的长度，然后减去n以此得到需要删掉的节点在正数时的序号，然后遍历一遍删掉就行了
我的AC代码
//时间复杂度O(n),空间复杂度O(1)
/**
* 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 cnt = 0;
ListNode* cur = head;
ListNode* dummyHead = new ListNode(-1,head);
while(cur != nullptr) {
cnt++;
cur = cur->next;
}
cnt = cnt - n;
cur = dummyHead;
while(cnt--) {
cur = cur->next;
}
cur->next = cur->next->next;
return dummyHead->next;
}
};标准答案的思路是双指针:
如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了
标准答案
//时间复杂度O(),空间复杂度O()
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
// ListNode *tmp = slow->next; C++释放内存的逻辑
// slow->next = tmp->next;
// delete nth;
return dummyHead->next;
}
};面试题 02.07. 链表相交 - 力扣（LeetCode）
思路:这道题主打的是题目描述很难理解，思路是先找出两个链表的长度，然后根据差值，设置两个指针，让这两个指针在同一起点出发，因为这题目判断的是链表相交，链表相交一个很重要的条件是相交的那个点的指针一定是相同的，这也是这题的易错点。起初我按照指针的值来判断，导致过不了样例。找到那个相交的指针以后，可以立即返回，因为后面一定是相同的（我自己的AC代码一直判断到结束，属于是画蛇添足了）
我的AC代码
//时间复杂度O(n+m),空间复杂度O(1)
/**
* 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) {
ListNode* a = headA;
ListNode* b = headB;
int indexa = 0;
int indexb = 0;
while(a != NULL) {
++indexa;
a = a->next;
}
while(b != NULL) {
++indexb;
b = b->next;
}
a = headA;
b = headB;
if(indexa > indexb) {
int tmp = indexa - indexb;
while(tmp--) {
a = a->next;
}
}
if(indexb > indexa) {
int tmp = indexb - indexa;
while(tmp--) {
b = b->next;
}
}
ListNode* slow = a;
ListNode* fast1 = a;
ListNode* fast2 = b;
int flag = 0;
while(fast1 != NULL) {
if((fast1 == fast2)) {
if(flag == 0) {
flag = 1;
slow = fast1;
}
}
else {
flag = 0;
slow = NULL;
}
fast1 = fast1->next;
fast2 = fast2->next;
}
return slow;
}
};标准答案
//时间复杂度O(n+m),空间复杂度O(1)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while (curA != NULL) { // 求链表A的长度
lenA++;
curA = curA->next;
}
while (curB != NULL) { // 求链表B的长度
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};142. 环形链表 II - 力扣（LeetCode）
思路：设置两个指针，快指针用来跑，慢指针用来记录环的入口，如果快指针跑的过程中遇到慢指针，那就说明有环，而且环的入口是慢指针。但是我不知道怎么从无限循环的状态中跑出来，只能设置一个cnt来记录，如果cnt > 1e4，那就说明已经跑完一圈了，那么肯定有环，而且慢指针不是入口，那慢指针就向后挪一位，如此反复就能得到答案了
推荐使用标准答案的快慢指针法
我的AC代码
/**
* 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) {
ListNode* dummyNode = new ListNode(-1,head);
ListNode* slow = dummyNode;
ListNode* fast = dummyNode;
while(slow->next != NULL) {
fast = slow->next;
int cnt = 0;
while(fast != NULL) {
if(cnt > 1e4){
break;
}
if(fast == slow) {
return slow;
}
else {
fast = fast->next;
}
++cnt;
}
slow = slow->next;
}
return NULL;
}
};标准答案
思路是先设置两个指针,指针slow每次移动一个节点,指针fast每次移动两个节点,这两个节点一定会相遇，在它们相遇的时候再设置两个指针,一个指针从头出发,一个指针从相遇的地方出发,这两个指针相遇的点就是入口,具体证明见代码随想录环形链表解析
/**
* 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) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL;
}
};
Comments NOTHING