文章目录
- 链表
- 合并两个有序链表
- 反转链表
- 复制带随机指针的链表
- 环形链表
- 环形链表II
- 相交链表
- 移除链表元素
- 链表中倒数第k个节点
- 链表分割
- 链表的回文结构
- 链表的中间节点
- 旋转链表
- 链表排序
- 链表求和 (逆序求)
- 链表求和II (正序求)
- 重排链表
- 奇偶链表
- 反转链表II <==> 链表内指定区间反转
- 删除链表中的节点
- 删除有序链表当中重复的元素I
- 删除有序链表当中重复的元素II
- 合并K个升序链表
- K个一组反转链表
- 交换链表中的节点
- 二进制链表转整数
- 链表随机节点
链表
合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/
1.定义一个哨兵位节点和一个tail节点标志尾节点
2.遍历两条有序链表,谁小就链接谁
3.最后还剩一条链表是没有遍历完成的,那么就让tail节点链接它
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//1.新建哨兵位节点ListNode* phead = new ListNode(-1);ListNode* tail = phead;//2.谁小就链接谁while(list1 && list2){if(list1->val > list2->val){tail->next = list2;tail = list2;list2 = list2->next;}else {tail->next = list1;tail = list1;list1 = list1->next;}}//3.判断谁还没有链接完if(list1) tail->next = list1;if(list2) tail->next = list2;return phead->next;}
};
反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
prev:记录前一个节点 cur:当前遍历到的节点 next:保存cur的下一个节点
- 先保存下一个节点 然后更改cur的指向,指向前一个节点
- 然后迭代往后走
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;//记录前一个节点ListNode* cur = head;//记录当前节点ListNode* next = nullptr;//记录下一个节点while(cur){next = cur->next;//先保存下一个节点cur->next = prev;//更改当前节点指向//prev cur next 迭代往后走prev = cur;cur = next;}return prev;}
};
复制带随机指针的链表
https://leetcode.cn/problems/copy-list-with-random-pointer/
1.在原链表节点之后拷贝一个节点
2.处理拷贝节点的random
指针
- 注意:拷贝节点的random指针指向的节点是其原链表节点的random指针指向的节点的下一个节点
- 坑点:有可能cur->random是空,也就是原来节点的random指针为空,那么当前拷贝节点的random指针也应该为空,否则cur->random->next 就会对空指针解引用!
3.分离两条链表
- 最好定义一个哨兵位节点和一个tail指针用于标记链接拷贝链表,
cur CopyCur next
三者的关系重新处理
class Solution {public:Node* copyRandomList(Node* head) {if(head == nullptr ) return nullptr;//1.在原节点后面copy一个节点Node* cur = head;while(cur){Node* copy = new Node(cur->val);//拷贝节点Node* next = cur->next;//cur copy next 链接cur->next = copy;copy->next = next;cur = next;//继续复制下一个节点}//2.处理拷贝节点的random指针cur = head;while(cur){Node* curCopy = cur->next;//cur的拷贝节点curCopy->random = cur->random == nullptr?nullptr:cur->random->next;cur = curCopy->next;}//3.拆离拷贝链表cur = head;Node* pnewHead = new Node(-1);//哨兵位Node* tail = pnewHead;while(cur){//cur copyCur next Node* copyCur = cur->next;Node* next = copyCur->next;copyCur->next = nullptr;//让拷贝节点独立存在tail->next = copyCur;tail = tail->next;//重新处理链接关系,向后走cur->next = next;cur = next;}return pnewHead->next;}
};
环形链表
https://leetcode.cn/problems/linked-list-cycle/description/
方法:使用快慢指针,二者从头开始走,一个一次走两步,一个一次走一步,当二者相遇的时候,说明有环
class Solution {
public:bool hasCycle(ListNode *head) {//链表为空//注意:一个节点也能成环! 自己指向自己if(!head) return false;//快慢指针ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇 注意:该条件不能放在上面!!!因为最初fast和slow都指向head,该条件应该放在下面if(slow == fast) return true;}return false;}
};
延申1:fast一次走两步,slow一次走一步,为什么一定能相遇?会不会在环里错过,永远遇不上
结论:slow一次走一步,fast一次走两步,如果存在环,slow和fast一定会在环内相遇
1.slow和fast,如果有环,一定是fast先进环,这时slow走了入环前距离的一半
2.随着slow进环,fast已经在环里面走了一段距离了(距离的多少跟环的大小有关)
- 假设slow进环的时候,slow和fast的距离为N,fast开始追赶slow
3.slow一次走一步,fast一次走两步,二者的距离变化为:N N- 1 N -2 … 0,当二者的距离变为0的时候,就是相遇了
延申2:fast一次走n步(n>2),slow一次走一步,fast和slow能相遇吗
结论:fast一次走n步(n>2),slow一次走一步,不一定会相遇
- 假设有环,fast一次走n步,slow一次走1步,fast和slow的距离不断减少n-1步
例子:假设fast一次走3步,如果slow进环之后,slow和fast的距离为N
如果N为偶数,那么二者之间的距离变化为:N N - 2 N - 4 … 2 0,此时二者相遇
如果N为计数,那么二者之间的距离变化为:N N - 2 N - 4 … 1 -1 ,二者距离变为-1,意味着fast超越了slow,此时fast和slow的距离为C -1 (假设C为环的大小)
- 如果C - 1 为偶数,那么下一轮fast可以追上slow,二者相遇
- 如果C - 1 为奇数,那么二者永远追不上
环形链表II
https://leetcode.cn/problems/linked-list-cycle-ii/description/
做法:
1.先看是否有环,快慢指针,fast一次走两步,slow一次走一步,如果存在环,fast和slow一定会相遇
2.假设相遇点为meetnode
,一个指针从链表的头开始走,一个指针从相遇点开始走,二者一次走一步,当二者相遇的时候,该位置就是入环节点
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return nullptr;//快慢指针ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇 注意:该条件不能放在上面!!!因为最初fast和slow都指向head,该条件应该放在下面if(slow == fast) {//分别从相遇点和链表头开始走,一次走一步 此时相遇就是入环位置ListNode* meet = slow;slow = head;while(slow != meet) {slow = slow->next;meet = meet->next;}return meet;}}return nullptr; //没有环}
};
相交链表
https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
方法1:将A链表的所有节点放到容器当中(要放地址,不能放值),然后遍历B链表,看能否在容器当中找到该元素,如果找到,那么该节点就是相交节点
class Solution {
public://方法1:用容器保存其中一个链表的节点,然后遍历另外一个链表进行比对ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {multiset<ListNode*> s;ListNode* cur = headA;while(cur) {s.insert(cur);cur = cur->next;}cur = headB;while(cur){cout << cur->val << endl;if(s.find(cur) != s.end()) return cur;cur = cur->next;}return nullptr;//不相交}
};
方法2:A中的每个结点和B分别比较(B和A比较也可以),看二者的地址是否一致 - O(N*M)
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;while(curA) //确定一个A节点{curB = headB;while(curB)//遍历整条B链表{if(curA == curB){return curA;}curB = curB ->next;}curA = curA->next;}return nullptr;}
};
方法3:
1.先统计两条链表的长度,假设二者长度差距为gap
2.长链表先往后走gap
步,然后长短链表一起往后走,如果相遇,那么就是相交节点
class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return nullptr;//1.统计两条链表的长度int lenA = 0;int lenB = 0;ListNode* cur = headA;while(cur) lenA++,cur = cur->next;cur = headB;