单链表的递归算法+变体
source link: https://forrestsu.github.io/posts/algorithm/leetcode/variants-singly-linkedlist-algo/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
单链表的递归算法+变体
2017年6月3日Preface
单链表的反转，按K反转等各种考点变体。
处理单链表时， 尽量采用递归实现：
1 因为递归代码简洁+优美，节省时间，并且不容易出错，是面试优选策略。
2 在面试时间比较宝贵的情况下，尽量预留时间展示自己的才能。
1 反转单链表(基础)
单链表结构定义如下：
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
方法一: 递归实现(尾插法)
class Solution {
public:
//尾插法
ListNode* reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) {
return head;
}
auto tail = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return tail; // became new head
}
};
方法二: 循环实现(头插法)
双指针,头插法:
ListNode* reverseList(ListNode *head) {
ListNode *pNewHead = NULL;
while(head != NULL){
auto pop = head;
head = head->next;
//插入新链表头部
pop->next = pNewHead;
pNewHead = pop;
}
return pNewHead; //链表的尾元素
}
2 变体一： 递归实现-从 m 到 n 中间节点的反转
上面我们使用递归，实现了反转整个链表的算法； 稍微改造下，只反转前k个元素(即递归深度到第k个元素，就可以返回)。
递归实现(从head 开始, 只反转前k个元素):
ListNode* reverseK(ListNode *head, int k) {
if (k <= 1) {
return head;
}
auto last = reverseK(head->next, k-1);
auto tail = head->next->next; //the tail list
head->next->next = head;
head->next = tail;
return last; //链表的尾元素
}
反转中间一部分[m,n], 再分析一下：
一种特殊情况是，m=1, 也就是反转前 n 个元素。
当 m = 2 ,我们把第一个节点去掉，就可以转化为上面的特殊情况了；
总结一下： 推广到一般的情况(m>1)，都可以转换为 m=1 的特殊情况处理。
// 反转中间一部分[m,n] 递归实现
ListNode* reverseBetween(ListNode *head, int m, int n) {
if (m == 1) {
return reverseK(head, n);
}
head->next = reverseBetween(head->next, m - 1, n - 1);
return head;
}
3 变体二: 按K个元素一组反转 (最后一组不足K个不反转)
我们先考虑下特殊情况:
1 链表元素总个数n 小于 k, 不做反转直接返回即可。
2 如果等于k个, 那么把当前链表按k反转，并返回新的head节点。
3 如果多余k个，我们先按照情形2处理前k个元素，剩下的(n-k)的链表当成一个子问题，执行步骤1,2,3.
最后这个子问题解决后，返回它的头指针 tailHead，
我们再把当前块的尾指针 head->next = tailHead 即可。
// golang implements
func reverseKGroup(head *ListNode, k int) *ListNode {
p := head
for i := 0; i < k; i++ {
// 不足k个直接返回
if p == nil {
return head
}
p = p.Next
}
newHead := reverseK(head, k)
// 超过K个节点部分, 又是一个按K反转的问题
head.Next = reverseKGroup(p, k)
return newHead
}
// 反转链表前 K 个元素
func reverseK(head *ListNode, k int) *ListNode {
if k == 1 {
return head
}
rear := reverseK(head.Next, k-1)
head.Next.Next = head
head.Next = nil
return rear
}
这个问题还有一个变体(从后往前分组), 这个题是 Shopee(2019年)的面试题：
解决办法：
1 先把整个链表全部反转，然后从新的head开始，按照k个一组，执行前插法；
注意：最后一个分组不足k个，逐个元素进行前插法，即可保证不足k个不反转。
/**[逆序] 从后往前, 每k个反转一次(不足k个不反转)（循环实现）
输入：1->2->3->4->5->6->7 k = 3
输出: 1->4->3->2->7->6->5
输入：1->2->3->4->5->6->7->8 k = 3
输出: 1->2->5->4->3->8->7->6
*/
ListNode* reverse(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *last = reverse(head->next);
head->next->next = head;
head->next = NULL;
return last; //became header
}
ListNode* reverseKGroup(ListNode *head, int k) {
ListNode * rhead = reverse(head);
int count = 0;
ListNode *cur = rhead;
ListNode *remain_list = rhead;
ListNode *newHead = NULL;
while (cur != NULL) {
++count;
ListNode *pre = cur;
cur = cur->next;
if (count == k) {
// 头插法
pre->next = newHead;
newHead = remain_list;
//move next
remain_list = cur;
count = 0;
}
}
//不足k个的部分,采用头插法
while (remain_list != NULL) {
ListNode *pop = remain_list;
remain_list = remain_list->next;
//头插法
pop->next = newHead;
newHead = pop;
}
return newHead;
}
正所谓万变不离其宗，我们先分析问题的特殊场景，然后推广到一般；
把一般情况转化为一个个特殊场景的子问题，最后使用递归就可以完美解决。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK