招聘去建设赌博类网站小说引流推广

目录

1.合并两个有序链表

2.反转链表

3.两两交换链表中的结点

---

1.合并两个有序链表

题目描述：

题目分析：

• 大问题：合并两个升序链表
• 策略：选出最小的结点，将剩下的部分和另一个链表拼接
• 子问题：合并剩下的部分和另一个升序链表
• 策略：选出最小的结点，将剩下的部分和另一个链表拼接

解决问题：

• 递归函数：ListNode* dfs(ListNode* list1, ListNode* list2);
• 函数功能：拼接两个升序链表。

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

代码示例：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {return dfs(list1, list2);}ListNode* dfs(ListNode* list1, ListNode* list2){if(!list1) return list2;if(!list2) return list1;ListNode* ret = nullptr;if(list1->val <= list2->val){ret = list1;ret->next = dfs(list1->next,list2);}else{ret = list2;ret->next = dfs(list2->next,list1);}return ret;}
};

2.反转链表

题目描述：

题目分析：

• 大问题：逆置n个节点的单链表
• 策略：逆置后面的n-1个节点，然后再和第一个逆置
• 子问题：逆置后面的n-1个节点
• 策略：逆置后面的n-2个节点，然后再和第二个逆置

解决问题：

• 递归函数：ListNode* dfs(ListNode* list)
• 功能：逆置list链表，并返回逆置之后最后一个结点的指针。

题目链接：206. 反转链表 - 力扣（LeetCode）

代码示例：

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head)return nullptr;return dfs(head);}// 逆置单链表ListNode* dfs(ListNode* list){if(list->next == nullptr){return list;}ListNode* ret = dfs(list->next);list->next->next = list;list->next = nullptr;return ret;}
};

3.两两交换链表中的结点

题目描述：

题目分析：

• 大问题：两两交换整个链表
• 策略：除了前两个结点，两两交换剩余的节点
• 子问题：两两交换剩余的结点
• 策略：除了前两个结点，两两交换剩余的结点

解决问题：

• 递归函数：ListNode* dfs(ListNode* head);
• 功能：两两交换head链表中的结点

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

代码示例：

class Solution {
public:ListNode* swapPairs(ListNode* head){return dfs(head);}ListNode* dfs(ListNode* head){if(!head || !head->next){return head;}ListNode* tmp = dfs(head->next->next);ListNode* ret = head->next; // 先保存一下要返回的节点head->next->next = head;head->next = tmp;return ret;}
};