递归——链表问题详解

合并两个有序链表

题目：合并两个有序链表

思路

划分为子问题，拿出最小的那个节点当做头节点，拼接剩下的当前节点尾部的节点和另一个链表的头节点相比较的更小的点，谁被拼接完了，就直接拼接另一条链表剩下的

C++代码

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1) return list2;if(!list2) return list1;if(list1->val<=list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list2->next, list1);return list2;}}
};

反转链表

题目：反转链表

思路

• 让当前节点后面的链表先逆值，并返回其头节点；
• 让当前节点添加到逆值后链表的尾部；

我们可以将链表看成一棵树

C++代码

/*** 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* reverseList(ListNode* head) {if(!head || !head->next){return head;}ListNode* newnode = reverseList(head->next);head->next->next = head;head->next = nullptr;return newnode;}
};

两两交换链表中的节点

题目：两两交换链表中的节点

思路

• 递归调用，交换当前节点的下两个节点
• 将当前节点的下一个节点作为新的头节点
• 将当前节点的下一个节点指向当前节点，实现交换
• 将当前节点的下一个节点指向递归操作的结果
• 返回新的头节点

C++代码

/*** 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 || !head->next){return head;}// 交换当前节点的下下个节点ListNode* tmp = swapPairs(head->next->next);// 将当前节点的下一个节点作为新头节点ListNode* newnode = head->next;// 更改节点间的关系head->next->next = head;head->next = tmp;return newnode;}
};