链表 25 K 个一组翻转链表 Leetcode每日一题,leetcode每日一题100题

❓ 25. K 个一组翻转链表

难度困难

给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。

k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。

示例 1

输入head [1,2,3,4,5], k 2
输出[2,1,4,3,5]

示例 2

输入head [1,2,3,4,5], k 3
输出[3,2,1,4,5]

提示

链表中的节点数目为 n1 < k < n < 50000 < Node.val < 1000

进阶你可以设计一个只用 O ( 1 ) O(1) O(1) 额外内存空间的算法解决此问题吗

思路

本题的目标非常清晰易懂不涉及复杂的算法但是实现过程中需要考虑的细节比较多。

先统计该链表中一共多少个节点 cnt从而可以计算出一共要反转 cnt/k 个子链表从而可以不用太关注边界定义一个空的头节点可以统一处理定义两个指针 l 和 r 分别指向已翻转链表的头和尾每翻转 k 个节点再重新计数。 代码(C、Java)

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* reverseKGroup(ListNode* head, int k) {        if(k  1) return head;        int cnt  0;        ListNode* p  head;        while(p ! nullptr){            cnt;            p  p->next;        }        p  new ListNode(0, head);        head  p;        ListNode* l  p->next;        ListNode* r  l;        for(int i  0; i < cnt / k; i){            int j  1;            while(j < k){                p->next  r->next->next;                r->next->next  l;                l  r->next;                r->next  p->next;                p->next  l;            }            p  r;            r  r->next;            l  r;        }        return head->next;    }};

Java

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val  val; } *     ListNode(int val, ListNode next) { this.val  val; this.next  next; } * } */class Solution {    public ListNode reverseKGroup(ListNode head, int k) {        if(k  1) return head;        int cnt  0;        ListNode p  head;        while(p ! null){            cnt;            p  p.next;        }        p  new ListNode(0, head);        head  p;        ListNode l  p.next;        ListNode r  l;        for(int i  0; i < cnt / k; i){            int j  1;            while(j < k){                p.next  r.next.next;                r.next.next  l;                l  r.next;                r.next  p.next;                p.next  l;            }            p  r;            r  r.next;            l  r;        }        return head.next;    }}

运行结果 复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n 为链表的长度。空间复杂度 O ( 1 ) O(1) O(1)我们只需要建立常数个变量。

题目来源力扣。

放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧
关注我LeetCode主页 / —力扣专栏每日更新

注 如有不足欢迎指正