两两交换链表结点
leetcode：24. 两两交换链表中的节点
迭代法
思路
第一步cur->next = cur->next->next
第二步cur->next->next = 原cur->next
第三步cur->next->next->next=原cur->next->next->next
注意用临时变量保存指针位置。
复杂度分析
时间复杂度：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) {
ListNode* dummyHead = new ListNode();
dummyHead->next = head;
ListNode* cur = dummyHead;
ListNode* tmp=NULL;
ListNode* tmp1=NULL;
while(cur->next && cur->next->next){
tmp = cur->next;
tmp1 = cur->next->next->next;
cur->next = cur->next->next; // step1
cur->next->next = tmp; // step2
cur->next->next->next = tmp1; // step3
cur = tmp;
}
return dummyHead->next;
}
};
递归法
暂时没看懂，略。
删除链表倒数第N个结点
leetcode：19. 删除链表的倒数第 N 个结点
双指针法
思路
最大问题就是找倒数第N，通过快指针比慢指针多走N步，定位到倒数第N个结点的前一个结点，然后就是简单链表删除操作。
复杂度分析
时间复杂度：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) {
ListNode* dummyHead = new ListNode();
dummyHead->next = head;
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
n++;
while( n-- && fast != NULL){
fast = fast->next;
}
while(fast != NULL){
slow = slow->next;
fast = fast->next;
}
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dummyHead->next;
}
};
链表相交
leetcode：面试题 02.07. 链表相交
两端对齐法
思路
对比指针是否相同来确定是否相交。
复杂度分析
时间复杂度：O(N)。
空间复杂度：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* curA = headA;
ListNode* curB = headB;
int lengthA = 0,lengthB = 0;
while(curA){
curA = curA->next;
lengthA++;
}
while(curB){
curB = curB->next;
lengthB++;
}
// 根据长度尾端对齐
curA = headA;
curB = headB;
int diff = lengthA-lengthB;
if(lengthA > lengthB){ // 如果A较长，移动A指针
while(diff--)
curA = curA->next;
}else{ // 如果B较长，移动B指针
diff = -diff;
while(diff--)
curB = curB->next;
}
// 从前往后依次对比指针
while(curA && curB){
if(curA == curB)
return curA;
else{
curA = curA->next;
curB = curB->next;
}
}
return NULL;
}
};
环形链表
leetcode：142. 环形链表 II
快慢指针法
思路
数学证明就不赘述了，卡哥已经讲的很清楚。有两个核心问题：
- 是否有环：快慢双指针遍历下去，指针相遇则有环。
- 如果有环，如何定位入口：快慢指针相遇时，此时再在头结点、相遇结点设置两个指针向后遍历，两指针相遇的结点就是入口结点。
复杂度分析
时间复杂度：O(N)。快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n。
空间复杂度：O(1)。
注意点
略
代码实现
/**
* 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* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next; // 快指针步长2
slow = slow->next; // 慢指针步长1
// 如果相遇，同时在表头、相遇点释放指针
if(fast == slow){
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};