做网站怎样实现网上支付,怎么样做小程序,如果做好招聘网站建设,茶山镇仿做网站目录
快慢指针#xff1a;
1. 相交链表#xff08;简单#xff09;
2. 环形链表#xff08;简单#xff09;
3. 快乐数#xff08;简单#xff09;
4. 环形链表 II#xff08;中等#xff09;
5. 删除链表的倒数第 N 个节点#xff08;中等#xff09;
递归迭…目录
快慢指针
1. 相交链表简单
2. 环形链表简单
3. 快乐数简单
4. 环形链表 II中等
5. 删除链表的倒数第 N 个节点中等
递归迭代双解法
1. 合并两个有序链表简单
1.1 递归求解
1.2 迭代求解
2. 反转链表简单
2.1 递归求解
2.2 迭代求解
3. 两两交换链表中的节点中等
3.1 递归求解
3.2 迭代求解
4. 合并 K 个升序链表困难
4.1 递归解法
4.2 迭代解法
综合题
1. 随机链表的复制中等
2. 重排链表中等
3. K个一组翻转链表困难 快慢指针
1. 相交链表简单
找两个链表的尾结点尾结点不相同则不相交。假设相交长短链表之间差距gap步。假设i指向长链表的头节点j指向短链表的头节点i先走gap步然后ij同时走每次走1步。当ij相遇时相遇点就是相交点。
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 找两个链表的尾结点尾结点不相同则不相交ListNode* tailA headA;ListNode* tailB headB;int lenA 0;int lenB 0;while (tailA-next){lenA;tailA tailA-next;}while (tailB-next){lenB;tailB tailB-next;}if (tailA ! tailB)return nullptr;// 判断长短链表ListNode* longList headA;ListNode* shortList headB;if (lenB lenA){longList headB;shortList headA;}// 长链表先走gap步int gap abs(lenA - lenB);while (gap--){longList longList-next;}// 同时走找交点while (longList ! shortList){longList longList-next;shortList shortList-next;}return longList;}
};
2. 环形链表简单
慢指针每次走1步快指针每次走2步慢指针进环后快指针一定能追上慢指针它们会在环中某点相遇。
为什么慢指针每次走1步快指针要每次走2步它们才能相遇
假设慢指针进环时快慢指针之间差距gap步。
如果快指针每次走2步每走一次它们之间的差距减1gap一定会减到0。
如果快指针每次走3步每走一次它们之间的差距减2。如果gap为偶数gap一定会减到0。如果gap为奇数gap会减到-1表示它们之间的距离变成C - 1C是环的周长如果C - 1是偶数它们会相遇如果C - 1是奇数它们永远不会相遇。
class Solution {
public:bool hasCycle(ListNode *head) {ListNode* slow head;ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;if (slow fast)return true;}return false;}
};
3. 快乐数简单 不是链表题但是和上一题“环形链表”类似慢指针每次走1步快指针每次走2步慢指针进环后快指针一定能追上慢指针它们会在环中某点相遇。如果相遇点为1则为快乐数否则不是快乐数。这里的指针表示的是值本身。
class Solution {
public:bool isHappy(int n) {int slow n;int fast bitSquareSum(n);while (slow ! fast){slow bitSquareSum(slow);fast bitSquareSum(bitSquareSum(fast));}return slow 1;}private:// 计算n的每一位的平方和int bitSquareSum(int n){int sum 0;while (n){int tmp n % 10;sum tmp * tmp;n / 10;}return sum;}
};
4. 环形链表 II中等
慢指针每次走1步快指针每次走2步慢指针进环后快指针一定能追上慢指针它们会在环中某点相遇。
假设在相遇点慢指针一共走了k步那么快指针一定一共走了2k步所以快指针比慢指针多走了k步。另外在相遇点快指针一定比慢指针在环中多走了若干圈。所以k一定是环的周长环中节点个数的整数倍。
此时让i指向相遇点j指向链表头节点它们之间差距k步慢指针走过的步数如果i到达了环的入口j也一定到达了环的入口因为它们之间差距k步k一定是环的周长的整数倍。
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;while (fast fast-next){fast fast-next-next;slow slow-next;if (fast slow) // 相遇{ListNode* i slow; // 相遇点ListNode* j head;while (i ! j){i i-next;j j-next;}return i;}}return nullptr;}
};
5. 删除链表的倒数第 N 个节点中等
快指针先走n步然后快慢指针同时走每次走1步。当快指针指向最后一个节点时慢指针指向倒数第n 1个节点。
例如删除链表的倒数第2个节点 class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* preHead new ListNode(0, head); // 哨兵节点ListNode* fast preHead; // 快指针ListNode* slow preHead; // 慢指针// 快指针先走n步while (n--){fast fast-next;}// 快慢指针同时走每次走1步直到快指针走到最后一个节点停止while (fast-next){fast fast-next;slow slow-next;}// 此时慢指针指向倒数第n1个节点// 让倒数第n1个节点的next域直接指向倒数第n-1个节点slow-next slow-next-next;return preHead-next;}
};
递归迭代双解法
1. 合并两个有序链表简单
1.1 递归求解 重复的子问题——函数头设计
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
子问题在做什么——函数体设计
选择两个链表的头节点中值较小的那一个作为最终合并的新链表的头节点然后将剩下的链表交给递归函数去处理。
比较list1-val和list2-val的大小假设list1-val较小list1-next mergeTwoLists(list1-next, list2);return list1;
递归出口
当某一个链表为空的时候返回另外一个链表。
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 nullptr)return list2;if (list2 nullptr)return list1;if (list1-val list2-val){list1-next mergeTwoLists(list1-next, list2);return list1;}else{list2-next mergeTwoLists(list1, list2-next);return list2;}}
};
1.2 迭代求解
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* preHead new ListNode; // 哨兵节点ListNode* tail preHead;// 取小的尾插while (list1 list2){if (list1-val list2-val){tail-next list1;tail tail-next;list1 list1-next;}else{tail-next list2;tail tail-next;list2 list2-next;}}if (list1){tail-next list1;}if (list2){tail-next list2;}return preHead-next;}
};
2. 反转链表简单
2.1 递归求解 重复的子问题——函数头设计
ListNode* reverseList(ListNode* head)
子问题在做什么——函数体设计
将当前结点之后的链表反转然后把当前结点添加到反转后的链表后面即可返回反转后的头节点。
ListNode* newHead reverseList(head-next);head-next-next head; head-next nullptr;return newHead;
递归出口
当前结点为空或者当前只有一个结点的时候不用反转直接返回。
class Solution {
public:ListNode* reverseList(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* newHead reverseList(head-next);head-next-next head;head-next nullptr;return newHead;}
};
2.2 迭代求解 class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre nullptr;ListNode* cur head;while (cur){ListNode* next cur-next;cur-next pre;pre cur;cur next;}return pre;}
};
3. 两两交换链表中的节点中等
3.1 递归求解 重复的子问题——函数头设计
ListNode* swapPairs(ListNode* head)
子问题在做什么——函数体设计
将从第三个节点开始的链表两两交换节点然后再把前两个节点交换一下链接上刚才处理过的链表并返回。
ListNode* tmp swapPairs(head-next-next);ListNode* newHead head-next; newHead-next head;head-next tmp;return newHead;
递归出口
当前结点为空或者当前只有一个结点的时候不用两两交换直接返回。
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* tmp swapPairs(head-next-next);ListNode* newHead head-next;newHead-next head;head-next tmp;return newHead;}
};
3.2 迭代求解 class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* preHead new ListNode(0, head); // 哨兵节点ListNode* cur preHead;// cur后面的两个节点交换while (cur-next cur-next-next){ListNode* node1 cur-next;ListNode* node2 cur-next-next;cur-next node2;node1-next node2-next;node2-next node1;cur node1;}return preHead-next;}
};
4. 合并 K 个升序链表困难
4.1 递归解法
分治的思想类似归并排序 划分两个子区间 分别对两个子区间的链表进行合并形成两个有序链表 合并两个有序链表
重复的子问题——函数头设计
ListNode* merge(vectorListNode* lists, int begin, int end)
子问题在做什么——函数体设计
划分两个子区间int mid (begin end) / 2;递归合并两个子区间 ListNode* l1 merge(lists, begin, mid); ListNode* l2 merge(lists, mid 1, end);合并两个有序链表return mergeTowList(l1, l2);
递归出口
当区间只有一个链表时不合并。另外当题目给出空链表时不合并。
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vectorListNode* lists, int begin, int end){if (begin end)return nullptr;if (begin end)return lists[begin];int mid (begin end) / 2;ListNode* l1 merge(lists, begin, mid);ListNode* l2 merge(lists, mid 1, end);return mergeTwoLists(l1, l2);}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){ListNode* preHead new ListNode; // 哨兵节点ListNode* tail preHead;// 取小的尾插while (list1 list2){if (list1-val list2-val){tail-next list1;tail tail-next;list1 list1-next;}else{tail-next list2;tail tail-next;list2 list2-next;}}if (list1){tail-next list1;}if (list2){tail-next list2;}return preHead-next;}
};
4.2 迭代解法
和“合并两个有序链表”类似就是取小的尾插。怎么判断K个链表未合并的头节点中最小的那个利用堆这个数据结构即可。把K个链表未合并的头节点放进一个小根堆堆顶就是最小的那个。
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {// 创建小根堆priority_queueListNode*, vectorListNode*, cmp heap;// 将所有头节点放进小根堆for (auto l : lists){if (l){heap.push(l);}}// 合并链表ListNode* preHead new ListNode; // 哨兵节点ListNode* tail preHead;while (!heap.empty()){// 取堆顶节点尾插tail-next heap.top();heap.pop();tail tail-next;// 将刚才合并的节点的下一个节点补充进堆if (tail-next){heap.push(tail-next);}}return preHead-next;}private:struct cmp{bool operator()(ListNode* n1, ListNode* n2){return n1-val n2-val;}};
};
综合题
1. 随机链表的复制中等 class Solution {
public:Node* copyRandomList(Node* head) {if (head nullptr)return nullptr;// A-B-C-null -- A-A-B-B-C-C-nullNode* cur head;while (cur){Node* copy new Node(cur-val); // 拷贝结点copy-next cur-next;cur-next copy;cur cur-next-next;}// 设置拷贝结点的random假如A的random域指向C就让A的random域指向Ccur head;while (cur){Node* copy cur-next;if (cur-random nullptr){copy-random nullptr;}else{copy-random cur-random-next;}cur cur-next-next;}// 将A、B、C链接在一起并且还原原链表Node* preHead new Node(0); // 哨兵节点Node* tail preHead;cur head;while (cur){tail-next cur-next;tail tail-next;cur-next cur-next-next;cur cur-next;}return preHead-next;}
};
2. 重排链表中等
把链表后半段反转再合并起来
链表长度是偶数1 2 3 4 2是中间节点
1 2
4 3
合并起来1 4 2 3
链表长度是奇数1 2 3 4 5 3是中间节点
1 2 3
5 44 5反转
合并起来1 5 2 4 3
class Solution {
public:void reorderList(ListNode* head) {ListNode* mid midNode(head);ListNode* l2 reverseList(mid-next);mid-next nullptr;ListNode* l1 head;mergeLists(l1, l2);}private:// 快慢指针找链表的中间节点如果节点个数为偶数取靠左的ListNode* midNode(ListNode* head){ListNode* fast head;ListNode* slow head;// 慢指针每次走1步快指针每次走2步// 如果节点个数为奇数当快指针指向最后一个节点时慢指针指向中间节点// 如果节点个数为奇数当快指针指向倒数第二个节点时慢指针指向靠左的中间节点while (fast-next fast-next-next){fast fast-next-next;slow slow-next;}return slow;}// 反转链表ListNode* reverseList(ListNode* head) {ListNode* pre nullptr;ListNode* cur head;while (cur){ListNode* next cur-next;cur-next pre;pre cur;cur next;}return pre;}// 合并链表void mergeLists(ListNode* l1, ListNode* l2){ListNode* cur1 l1;ListNode* cur2 l2;while (cur1 cur2){ListNode* next1 cur1-next;ListNode* next2 cur2-next;cur1-next cur2;cur2-next next1;cur1 next1;cur2 next2;}}
};
3. K个一组翻转链表困难
头插法。 class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {// 求出需要翻转多少组int n 0;ListNode* cur head;while (cur){cur cur-next;n;}n / k;// 重复n次长度为k的链表翻转ListNode* preHead new ListNode; // 哨兵节点ListNode* pre preHead;cur head;for (int i 0; i n; i){ListNode* tmp cur;for (int j 0; j k; j){ListNode* next cur-next;cur-next pre-next;pre-next cur;cur next;}pre tmp;}// 把不需要翻转的部分接上pre-next cur;return preHead-next;}
};
