给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
说明：
1. 你需要自行定义链表结构，将输入的数据保存到你的链表中；
2. 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；
3. 你的算法只能使用常数的额外空间。
[编程题]每K个一组反转链表
为什么我的代码在LeetCode-25通过了，这里测试用例也通过了，时间复杂度是O(n)。可是提交总提示运行超时呢，一个测试用例都没过，就离谱
import java.io.*;
class Node{
int val;
Node next;
public Node(int val){ this.val = val;}
public Node(int val, Node node){
this.val = val;
this.next = node;
}
}
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nums = br.readLine().split(" ");
Node head = new Node(0);
Node pre = head;
for(int i = 0; i < nums.length; i++){
Node cur = new Node(Integer.parseInt(nums[i]));
pre.next = cur;
pre = cur;
}
head = head.next;
int k = Integer.parseInt(br.readLine());
br.close();
Node newHead = reversek(head, k, nums.length);
while(newHead != null){
System.out.print(newHead.val + " ");
newHead = newHead.next;
}
}
public static Node reversek(Node head, int k, int len){
if(k == 1 || len == 1)
return head;
int sum = len;
Node cur = head;
Node pre = null;
Node tail = head;
int curNum = 0;
boolean isFirst = true;
Node newTail;
Node temp;
while(sum >= k){
newTail = cur;// 记录下一趟的尾结点
for(;curNum < k;curNum++){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
if(isFirst) head = pre;
else{
tail.next = pre;
tail = newTail;
}
isFirst = false;
sum -= k; // 一趟反转结束，总长-k
curNum = 0; // 重置为0
pre = null; // 重置为null
}
tail.next = cur;
return head;
}
}
发表于 2021-04-03 23:02:52
回复(0)
/*
思路：写一个反转函数，每次都把相应长度的字符串进行翻转，反转可以用revese方法，不合题意
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int k = Integer.parseInt(br.readLine());
if(str.length < k)
for(int i = 0;i<str.length;i++){
System.out.print(str[i] + " ");
if(i==str.length-1)
System.out.println();
}
else{
int n = str.length/k;
for(int i = 0;i<n;i++){
int left = 0 + i*k;
int right = i*k + k -1;
while(left < right){//反转
String temp = str[left];
str[left] = str[right];
str[right] = temp;
left++;right--;
}
}
for(int i = 0;i<str.length;i++){
System.out.print(str[i] + " ");
if(i==str.length-1)
System.out.println();
}
}
}
} 不合题意的解法
发表于 2020-05-22 15:36:43
回复(0)
小菜鸡的暴力思路
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] s = str.split(" ");
int k = sc.nextInt();
//如果k== s.length，则整体倒序输出
if (k == s.length){
for (int i = s.length-1; i >= 0; i--) {
System.out.print(s[i]+" ");
}
//如果k<s.length
}else if (k < s.length){
int index = 0;
int len = s.length;
//当剩余长度大于等于k时，反转输出
while (len >= k){
for (int i = index+k-1; i >= index; i--) {
System.out.print(s[i]+" ");
}
//index更新，长度剪短
index += k;
len -= k;
}
//剩余的长度小于K，则无法反转，要正序输出
for (int i = index; i < s.length; i++) {
System.out.print(s[i]+" ");
}
//如果k>s.length，不做反转
}else {
for (int i = 0; i < s.length; i++) {
System.out.print(s[i]+" ");
}
}
}
}
发表于 2020-04-16 10:14:21
回复(0)
import java.util.*;
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val=val;
}
}
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
String []s=sc.nextLine().split(" ");
int [] nums=new int[s.length+1];
nums[0]=-1;
for(int i=0;i<s.length;i++){
nums[i+1]=Integer.parseInt(s[i]);
}
int k=sc.nextInt();
int times=s.length/k;
ListNode head=new ListNode(nums[0]);
ListNode res=head;
for(int now=1;now<=times;now++){
for(int j=now*k;j>=(now-1)*k+1;j--){
ListNode next=new ListNode(nums[j]);
head.next=next;
head=next;
}
}
if(s.length%k!=0){
for(int y=times*k+1;y<=s.length;y++){
ListNode next=new ListNode(nums[y]);
head.next=next;
head=next;
}
}
res=res.next;
while(res!=null){
System.out.print(res.val+" ");
res=res.next;
}
}
}
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val=val;
}
}
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
String []s=sc.nextLine().split(" ");
int [] nums=new int[s.length+1];
nums[0]=-1;
for(int i=0;i<s.length;i++){
nums[i+1]=Integer.parseInt(s[i]);
}
int k=sc.nextInt();
int times=s.length/k;
ListNode head=new ListNode(nums[0]);
ListNode res=head;
for(int now=1;now<=times;now++){
for(int j=now*k;j>=(now-1)*k+1;j--){
ListNode next=new ListNode(nums[j]);
head.next=next;
head=next;
}
}
if(s.length%k!=0){
for(int y=times*k+1;y<=s.length;y++){
ListNode next=new ListNode(nums[y]);
head.next=next;
head=next;
}
}
res=res.next;
while(res!=null){
System.out.print(res.val+" ");
res=res.next;
}
}
}
编辑于 2019-09-07 14:00:55
回复(0)
利用递归的方法最简单：
import java.util.*;
class ListNode{
int val;
ListNode next = null;
ListNode(int val){
this.val = val;
}
}
public class reverseKlist{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()){
String[] str = sc.nextLine().split(" ");
int k = Integer.valueOf(sc.nextLine());
ListNode pre = new ListNode(Integer.valueOf(str[0]));
ListNode head = pre;
for (int i=1;i<str.length;i++){
ListNode node = new ListNode(Integer.valueOf(str[i]));
pre.next = node;
pre = node;
}
pre.next = null;
head = reverse(head, k);
while (head != null){
System.out.print(head.val+" ");
head = head.next;
}
}
}
public static ListNode reverse(ListNode head, int k){
ListNode tmp = head;
for (int i=1;i<k&&tmp!=null;i++)
tmp = tmp.next;
if (tmp == null) return head;
ListNode Lhead = tmp.next;
tmp.next = null;
ListNode newHead = revK(head);
ListNode newLHead = reverse(Lhead, k);
head.next = newLHead;
return newHead;
}
public static ListNode revK(ListNode head){
ListNode tmp = null, pre = null;
while (head != null){
tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
}
发表于 2019-09-01 11:33:18
回复(0)
方法一：反正都要翻转，链表操作麻烦还不如翻转字符串先，再构造一个链表。就是使用栈翻转字符串
import java.util.*;
class ListNode{
int val;
ListNode next = null;
ListNode(int val){
this.val=val;
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String[] str= sc.nextLine().split(" ");
int k=sc.nextInt();
int n =str.length;
Stack<String> ss = new Stack<String>();//以下就是翻转啦
for(int j=0;j+k<=n;j+=k){
for(int i=j;i<j+k;i++) ss.push(str[i]);
for(int i=j;i<j+k;i++) str[i]=ss.pop();
}
ListNode list = create(str,n);
for(int i=0;i<n;i++){
System.out.print(list.val+" ");
list=list.next;
}
}
public static ListNode create(String[] str,int n){
ListNode preList=new ListNode(0);
ListNode list=preList;
for(int i=0;i<n;i++){
list.next=new ListNode(Integer.parseInt(str[i]));
list=list.next;
}
return preList.next;
}
}
编辑于 2019-08-30 19:28:50
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-09-29 16:44:01 -
2022-09-19 12:47:31
-
2022-09-18 22:38:09
-
2022-09-14 20:33:40 -
2022-09-12 00:12:30
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
