前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【力扣刷题】25. K 个一组翻转链表

【力扣刷题】25. K 个一组翻转链表

作者头像
jayjay
发布2022-11-02 16:53:16
2550
发布2022-11-02 16:53:16
举报
文章被收录于专栏:jay_blog

一、题目描述

来源:力扣(LeetCode)

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

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

进阶:

你可以设计一个只使用常数额外空间的算法来解决此问题吗? 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。     示例 1:

image.png
image.png
代码语言:javascript
复制
输入: head = [1,2,3,4,5], k = 2
输出: [2,1,4,3,5]

示例 2:

image.png
image.png
代码语言:javascript
复制
输入: head = [1,2,3,4,5], k = 3
输出: [3,2,1,4,5]

示例 3:

代码语言:javascript
复制
输入: head = [1,2,3,4,5], k = 1
输出: [1,2,3,4,5]

  示例 4:

代码语言:javascript
复制
输入: head = [1], k = 1
输出: [1]

提示:

  • 列表中节点的数量在范围 sz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

二、思路分析

  1. 统计链表的长度
  2. 计算链表翻转的次数 reverse_times=len/k;
  • 如果翻转次数为0,直接返回原链表即可。
  1. 定义多个变量
  • cur_time保存当前翻转的次数(可以用来确定翻转次数)
  • nhead虚拟头结点(一般链表题中都可定义一个不包含数据的哨兵头结点)
  • knext保存下一次翻转的链表头结点(防止后面的链表数据丢失)
  • cur_head当前需要翻转的部分链表的头结点,实际上是头部结点的前一个结点(便于做局部翻转)。
  • cur_tail当前翻转的部分链表的尾部结点,用于在翻转完成后,与knext进行连接,保证数据不会被丢失。
  1. 执行链表的翻转
    1. 将knext指向下一次翻转时候的链表头结点
    1. 使用头插法进行反转(注意要用cur_tail保存局部链表的第一个结点,翻转完成后,它将处于局部链表的最后一个位置,然后将它与后面的链表连接起来)
    1. 将尾部结点重新赋值给头部结点,并且让尾部结点的next指针指向knext
    1. 翻转次数+1
    1. 返回nhead.next;

三、代码实现

代码语言:javascript
复制
/**
 * 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) {
        int len=0;                  //统计链表的长度
        ListNode plen=head;
        while(plen!=null){
            len++;
            plen=plen.next;
        }

        int reverse_times=len/k;     //计算链表的翻转次数
        if(k<=1 || reverse_times==0){
            return head;
        }

        ListNode knext=head;         //保存下一次翻转时候的链表头结点
        int cur_times=0;      //保存当前翻转次数
        ListNode nhead=new ListNode(-1);    //虚拟头结点,不包含任何数据
        ListNode cur_head=nhead;
        cur_head.next=head;
        ListNode cur_tail=null;
        while(cur_times<reverse_times){
            //将knext指向下一次翻转时候的链表头结点
            for(int i=0;i<k;i++){
                knext=knext.next;
            }

            //使用头插法进行反转            
            ListNode p=cur_head.next;        //保存当前需要头插的结点
            cur_tail=cur_head.next;
            ListNode next=null;         //保存反转时下一个结点的指针
            for(int i=0;i<k;i++){
                next=p.next;           
                p.next=cur_head.next;
                cur_head.next=p;
                p=next;
            }
            //将尾部结点重新赋值给头部结点,并且让尾部结点的next指针指向knext
            cur_head=cur_tail;
            cur_tail.next=knext;
            // System.out.println("3 "+knext.val);
            cur_times++;
        }        
        return nhead.next;
    }
}

四、运行结果

image.png
image.png

总结

参考了别人的解题,这道题在于确定要反转多少次,然后分组进行头插,剩下的接上就行了

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、思路分析
  • 三、代码实现
  • 四、运行结果
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档