Reverse Nodes in k-Group——解题报告

╰半夏微凉° 2022-08-08 06:50 11阅读 0赞

【题目】

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,  
Given this linked list: `1->2->3->4->5`

For k = 2, you should return: `2->1->4->3->5`

For k = 3, you should return: `3->2->1->4->5`

【分析】

先找到第k个节点，然后递归反转第k节点后面的链表，然后反转head到第k个节点的部分（此时使用非递归方式反转更加方便）。

【题目】

运行时间30ms

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            ListNode* p = getKthNode(head, k);
            if(head == NULL || p == NULL)
                return head;
                
            ListNode* res = reverseKGroup(p->next, k);
            p->next = NULL;
            // 从head到res反转
            while(head)
            {
                ListNode* cur = head->next;
                head->next = res;
                res = head;
                head = cur;
            }
            return res;
        }
        
        ListNode* getKthNode(ListNode* head, int k)
        {
            for(int i = 0; head && i < k - 1; i++)
            {
                head = head->next;
            }
            return head;
        }
    
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 Reverse Nodes in k-Group

Reverse Nodes in k-Group 文章目录 Reverse Nodes in k-Group 题目分析

浅浅的花香味﹌/ 2023年06月06日 10:54/ 0 赞/ 9 阅读

相关 LeetCode - Hard - 25. Reverse Nodes in k-Group

Topic Linked List Description [https://leetcode.com/problems/reverse-nodes-in-

Dear 丶/ 2023年01月07日 01:22/ 0 赞/ 8 阅读

相关 leetcode 25 Reverse Nodes in k-Group

给一个链表，每k个节点一组进行反转，输出反转后的链表 hard难度，但突破点很好找，具体解体思路，看下面代码中每行注释 public class LC25 {

╰+攻爆jí腚メ/ 2022年12月20日 11:15/ 0 赞/ 94 阅读

相关 Reverse Nodes in k-Group——解题报告

【题目】 Given a linked list, reverse the nodes of a linked list k at a time and retu

╰半夏微凉°/ 2022年08月08日 06:50/ 0 赞/ 12 阅读

相关 Swap Nodes in Pairs ——解题报告

【题目】 Given a linked list, swap every two adjacent nodes and return its head.

忘是亡心i/ 2022年08月08日 06:50/ 0 赞/ 25 阅读

相关 Reverse Nodes in k-Group--LeetCode

题目： Given a linked list, reverse the nodes of a linked list k at a time and return it

水深无声/ 2022年08月07日 10:46/ 0 赞/ 12 阅读

相关 [leetcode javascript解题]Swap Nodes in Pairs

leetcode 24题 “ Swap Nodes in Pairs”描述如下： > Given a linked list, swap every two adjacent

小鱼儿/ 2022年07月13日 03:18/ 0 赞/ 132 阅读

相关 leetcode 25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modif

缺乏、安全感/ 2022年06月09日 08:13/ 0 赞/ 107 阅读

相关 [解题报告]A Change in Thermal Unit

题目大意题目原文：[http://uva.onlinejudge.org/external/119/11984.pdf][http_uva.onlinejudge.or

逃离我推掉我的手/ 2022年01月07日 12:49/ 0 赞/ 122 阅读

相关 LeetCode-25- Reverse Nodes in k-Group

算法描述： Given a linked list, reverse the nodes of a linked list k at a time and return it

痛定思痛。/ 2021年12月15日 14:01/ 0 赞/ 142 阅读