正文

Leetcode25--->Reverse Nodes in k-Group(以k个节点为段，反转单链表)

IP云V管理员/2022-11-30/2 阅读

11/30

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目：给定一个单链表，一次反转k个节点，最终返回翻转后的链表的头节点；如果链表不足k个，则不变

举例：

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

解题思路：

1. 首先要确定链表的头节点newHead;即如果链表的节点个数大于k,则头节点为第k个节点；否则头节点不变；

2. 区分每一段，即确定段的开始和结尾；当前段的开始start, 段的结尾可以用k确定；下一段的开始为end;

3. 每k个节点之间的反转；

4. 段与段之间的连接，prevNode指向前一段的最后一个节点；

 /**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) { val = x; }

  * }

  */

 public class Solution {

     public ListNode reverseKGroup(ListNode head, int k) {

         if(head == null || k <= 1)

             return head;

         ListNode begin = head; // begin是当前段的开始

         ListNode end = begin;  // end是下一段的开始

         ListNode newHead = begin;  // 新的链表头

         ListNode prevNode = head;  // 是上一段的最后一个节点

         int flag = 0;  // 记录是第几段

         while(end != null){

             int count = 1;

             while(end.next != null && count < k){

                 end = end.next;

                 count ++;

             }

             if(count == k){

                 if(flag == 0){

                     newHead = end;

                 }

                 flag ++;

                 if(flag > 1){  // 不是第一段时就需要段与段之间的连接

                     prevNode.next = end;  // 段和段之间进行连接

                     prevNode = begin;

                 }

                 end = end.next;  // 下一个段的开始

                 ListNode prev = null;

                 int i = 0;

                 while(i < k){  // 链表的反转

                     ListNode nextNode = begin.next;

                     begin.next = prev;

                     prev = begin;

                     begin = nextNode;

                     i++;

                 }

                 begin = end;   // 下一个段的开始

                 prevNode.next = end;  // 两个段之间连接，是为了避免下一段节点数不足k个，则不能使用第30行代码来连接段

             }

             else

                 break;

         }

         return newHead;

     }

 }

Leetcode25--->Reverse Nodes in k-Group(以k个节点为段，反转单链表)的更多相关文章

以K个为一组反转单链表，最后不足K个节点的部分也反转
package StackMin.ReverseList_offer16; public class ReverseKgroup_extend_offer16 { /** * 分组反转单链表,最后不足 ...

Reverse反转算法＋斐波那契数列递归＋Reverse反转单链表算法－－C++实现
Reverse反转算法 #include <iostream> using namespace std; //交换的函数 void replaced(int &a,int &amp ...

[Leetcode] Reverse nodes in k group 每k个一组反转链表
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If ...

leetcode：Reverse Nodes in k-Group（以k为循环节反转链表）【面试算法题】
题目: Given a linked list, reverse the nodes of a linked list k at a time and return its modified list ...

LeetCode25 Reverse Nodes in k-Group
题意: Given a linked list, reverse the nodes of a linked list k at a time and return its modified list ...

以k个元素为一组反转单链表
Example: input: 1->2->3->4->5->6->7->8->NULL and k = 3 output:3->2->1- ...

LeetCode 25. k个一组翻转链表（Reverse Nodes in k-Group）
题目描述给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表. k 是一个正整数,它的值小于或等于链表的长度.如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序. 示例 : 给定 ...

【Reverse Nodes in k-Group】cpp
题目: Given a linked list, reverse the nodes of a linked list k at a time and return its modified list ...

【链表问题】打卡9：将单链表的每K个节点之间逆序
前言以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获.每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢. 注:如果代码排版出现了问题麻烦通知我下 ...

随机推荐

javaweb-servlet生成简单的验证码
package com.serv; import java.awt.Color; import java.awt.Graphics; import java.awt.image.BufferedIma ...

1.2 the structure of a compiler
Compiler 1.2 the structure of a compiler Compiler : analysis and synthesis syntactically 语法上的 sema ...

LR脚本示例之常用函数
1.变量和参数的设置 //将IP地址和端口放入到参数中lr_save_string("127.0.0.1:1080","ip"); //退出脚本建议使用lr_e ...

洛谷 P3387 【模板】缩点
题目背景缩点+DP 题目描述给定一个n个点m条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大.你只需要求出这个权值和. 允许多次经过一条边或者一个点,但是,重复经过的点,权值只 ...

This implementation is not part of the Windows Platform FIPS validated cryptographic algorithms while caching
今天运行自己的网站时报了这样一个错误,很是纳闷,这个网站运行了这么久,怎么报这个错呢,原来是做缓存的时候用到了基于windows平台的加密算法.解决方法如下: 删除注册表下的这个节点即可.删除HKEY ...

Android（java）学习笔记115：BroadcastReceiver之 Android广播机制
Android广播机制 android系统中有各式各样的广播,各种广播在Android系统中运行,当"系统/应用"程序运行时便会向Android注册各种广播.Android接收到广 ...

wxWidgets：处理wxEVT
我们仍然以继承于wxFrame的MyFrame作为例子. MyFrame.h: class MyFrame : public wxFrame { ...... private: ...... void ...

【转】树莓派3代3.5寸触摸屏驱动的安装（通过ssh安装）
这是用到的配件的树莓派3代烧录好系统后,启动的树莓派,我的树莓派已经在一开始通过路由器和局域网,登陆了ssh,设置好了开机就能自动连接到电脑的360wifi,所以无论到哪里,只要自己的笔记本电脑还 ...

java 自定义容器，实现foreach
import java.util.Arrays; import java.util.Iterator; public class ArrayList implements Iterable<In ...

python 函数内使用全局变量
x = def change_global(): global x x = x + change_global() print(x) result: 2

相关阅读

目录[+]