[数据结构与算法] [LeetCode] 25. K个一组翻转链表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> [LeetCode] 25. K个一组翻转链表 -> 正文阅读

[数据结构与算法][LeetCode] 25. K个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

/**
 * 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 {
private:
    ListNode* reverse(ListNode* node) {
        ListNode* tmp;
        ListNode* prev = nullptr;
        ListNode* cur = node;
        while(cur) {
            tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

public:
    //递归  
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        if(head == nullptr) return head;
        for(int i = 0; i < k - 1; i++) {
            cur = cur->next;
            if(cur == nullptr)
                return head;
        }
        ListNode* tmp = cur->next;
        cur->next = nullptr;
        //部分链表反转后的头节点
        ListNode* newHead = reverse(head);
        //递归
        head->next = reverseKGroup(tmp, k);
        return newHead;

    }
};

修改问法：如果最后不满足k个的剩余节点也要反转呢？

修改一处即可

class Solution {
private:
    ListNode* reverse(ListNode* node) {
        ListNode* tmp;
        ListNode* prev = nullptr;
        ListNode* cur = node;
        while(cur) {
            tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

public:
    //递归  
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        if(head == nullptr) return head;
        for(int i = 0; i < k - 1; i++) {
            cur = cur->next;
            if(cur == nullptr)
                return reverse(head); //!!!!!!!!!!!!!!!!!这里返回的是反转后的头节点，而非原来的头节点
        }
        ListNode* tmp = cur->next;
        cur->next = nullptr;
        //部分链表反转后的头节点
        ListNode* newHead = reverse(head);
        //递归
        head->next = reverseKGroup(tmp, k);
        return newHead;

    }
};