首页 > 试题广场 >

k个一组翻转链表

[编程题]k个一组翻转链表
  • 热度指数：650 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给你一个链表，每 k 个节点一组进行翻转，请返回翻转后的链表。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5


输入描述:
第一行：依次输入链表中的各个元素，以"#"结束

第二行：每组数量k


输出描述:
处理后的链表中的各个元素，以"->"连接
示例1

输入

1 2 3 4 5 #
2

输出

2->1->4->3->5
示例2

输入

1 2 3 4 5 #
3

输出

3->2->1->4->5
算法知识视频讲解
添加回答
宇宙警备队头像 宇宙警备队 
import java.util.*;

public class Main {
    static class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val = val;
        }
    }
        // 这里全是输入处理
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.nextLine();
            int k = in.nextInt();
            ListNode head = new ListNode(-1);
            ListNode p = head;
            String[] strArray = str.split(" ");
            for(int i = 0; i < strArray.length - 1; i++){
                p.next = new ListNode(Integer.parseInt(strArray[i]));
                p = p.next;
            }
            head = reverseK(head.next, k);
            printList(head);
        }
    }
        // 输出处理
    private static void printList(ListNode head) {
        while(head != null){
            System.out.print(head.val);
            if(head.next != null){
                System.out.print("->");
            }
            head = head.next;
        }
    }
        // 核心程序
    private static ListNode reverseK(ListNode head, int k) {
        if(k == 1 || head == null || head.next == null){
            return head;
        }
        ListNode a = head, b = head;
        for(int i = 0; i < k; i++){
            if(b == null){
                return head;
            }
            b = b.next;
        }
        ListNode newHead = reverse(a, b);
        head.next = reverseK(b, k);
        return newHead;
    }

    private static ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null, cur = a;
        while(cur != b){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return  pre;
    }
}

编辑于 2021-05-25 22:01:12 回复(0)
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:bilibili📺- k 个一组翻转（slice+reverse）
leetcode25. K 个一组翻转链表 
//leetcode25. K 个一组翻转链表
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 2){
        let arr = inArr[0].split(' ').map(e=>+e)
        arr.pop()
        let k = +inArr[1]
        let res= reverseKGroup(arr, k).join('->')
        console.log(res)
    }
})
var reverseKGroup = function(arr, k) {
    let len = arr.length
    let cnt = Math.floor(len/k)
    let curArr  = [...arr]
    for (let i = 0; i < cnt; i++) {
        let lastArr = curArr.slice(k*(i+1))
        curArr = curArr.slice(0,i*k).concat(curArr.slice(i*k,k*(i+1)).reverse(),lastArr)
    }
    return curArr
};

发表于 2020-02-27 14:59:20 回复(0)
Java
joduas头像 joduas 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {


    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String arrayStr = in.nextLine();
            int k = in.nextInt();
            ListNode head = new ListNode(0);
            ListNode p = head;
            String[] array =  arrayStr.split(" ");
            for (int i = 0; i < array.length - 1; i++) {
                p.next = new ListNode(Integer.parseInt(array[i]));
                p = p.next;
            }

            // 反转链表
            head = reverseK(head.next, k);
            printList(head);
        }
    }

    private static ListNode reverseK(ListNode head, int k) {
        // 如果反向反转  此处需要将整个链表反转

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;
        // 循环操作
        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) {
                end  = end.next;
            }
            if (end == null) {
                break;
            }
            // 开始切断连线

            ListNode start = pre.next;
            ListNode nextStart = end.next;
            end.next = null;


            pre.next = reverseKGroup(start);
            start.next = nextStart;
            pre =  start;
            end = pre;

        }
        return dummy.next;

    }
    // 反转链表  改变指针方向
    private static ListNode reverseKGroup(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next ;
            curr.next = pre;
            pre = curr;
            curr = next;

        }
        return pre;
    }
    /**
     * 2->1->4->3->5
     */
    private static void printList(ListNode head) {
        StringBuilder sd = new StringBuilder();

        while (head != null) {
            sd.append(head.val);
            head = head.next;
            if (head != null ) {
                sd.append("->");
            }
        }
        System.out.println(sd.toString());

    }
}

编辑于 2024-01-23 10:41:08 回复(0)
来学习的小张头像 来学习的小张 
import java.util.*;
public class Main{
    public static void reverse(String[] str,int start,int end){
        while(start < end){
            String temp = str[start];
            str[start] =  str[end];
            str[end] = temp;
            start++;
            end--;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = sc.nextInt();
        //将输入字符串以空格进行分隔
        String[] strArr = str.split(" ");
        int start = 0;
        while(start + n - 1 < strArr.length - 1){
            reverse(strArr,start,start + n - 1);
            start += n;
        }
        for(int i = 0;i < strArr.length - 2;i++){
            System.out.print(strArr[i] + "->");
        }
        //将最后一个数字打印输出
        System.out.println(strArr[strArr.length - 2]);
    }
}

发表于 2022-04-08 08:53:34 回复(0)
牛客4787头像 牛客4787
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


int main(){
    vector<string> arr;
    string ch;
    while(cin >> ch){
        if (ch == "#"){
            break;
        }
        arr.emplace_back(ch);
    }
    int k = 0;
    cin >> k;
    int start = 0;
    while(start + k <= (int)arr.size()){
        reverse(arr.begin() + start, arr.begin() + start + k);
        start += k;
    }
    cout << arr[0];
    for (unsigned long i = 1; i < arr.size(); ++i){
        cout << "->" << arr[i];
    }
    cout << endl;
    return 0;
}

发表于 2022-01-26 18:00:10 回复(0)
蹇之途头像 蹇之途 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ListNode dummy = new ListNode();
        ListNode old = dummy;
        while(sc.hasNext()) {
            String in = sc.next().trim();
            if(in.equals("#")) break;
            while(dummy.next != null) {
                dummy = dummy.next;
            }
            dummy.next = new ListNode(Integer.parseInt(in));
        }
        int k = sc.nextInt();
        ListNode head = solution(old.next,k);
        while(head.next != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
        System.out.print(head.val);
    }

    private static ListNode solution(ListNode head, int k) {
        if(head == null) return head;
        int size = 0;
        for(ListNode i = head; i != null; i = i.next, size ++);
        ListNode dmy = new ListNode(), oldHead = dmy, cur = head, h;
        while(k <= size) {
            size -= k;
            for(int i = 0; i < k; i++) {
                h = cur;
                cur = cur.next;
                h.next = dmy.next;
                dmy.next = h;
            }
            while(dmy.next != null) {
                dmy = dmy.next;
            }
        }
        if(cur != null) dmy.next = cur;
        return oldHead.next;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
        ListNode() {}
    }
}

发表于 2021-06-28 20:26:30 回复(0)
庖丁解牛-解牛刀法头像 庖丁解牛-解牛刀法
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        int k=Integer.parseInt(sc.nextLine());
        int w=a.indexOf('#');
        a=a.substring(0,w);
        String[] b=a.split(" ");
        int len=b.length;
        String[] c=new String[len];
        int q=0;
        for(int i=0;i<b.length;i++){
            if((len-i)>=k){
                for(int j=k-1;j>=0;j--){
                    c[q++]=b[i+j];
                }
                i=i+k-1;
            }else{
                  c[q++]=b[i];
            }
        }
        for(int i=0;i<c.length-1;i++){
            System.out.print(c[i]+"->");
        }
        System.out.print(c[c.length-1]);
    }
}
发表于 2020-10-11 16:15:06 回复(0)
想念自由风头像 想念自由风 
while 1:
    try:
        inp = list(input().split())
        inp = inp[0:len(inp)-1]
        h = len(inp)
        k = int(input())
        n = h//k
        if n*k!=h:
            for ii in range(n):
                y = inp[k*ii:k*(ii+1)]
                y.reverse()
                print('->'.join(y),end='->')
            print('->'.join(inp[n*k:]))
        else:
            for ii in range(n-1):
                y = inp[k*ii:k*(ii+1)]
                y.reverse()
                print('->'.join(y),end='->')
            y = inp[k*(n-1):k*n]
            y.reverse()
            print('->'.join(y))
    except:
        break
能过，但写的很麻烦，有没有老哥可以不用分情况的
发表于 2020-09-13 17:15:59 回复(0)
CarmenLo99头像 CarmenLo99
``` 
let nums = readline().split(' ').slice(0,-1)
let k = readline()
let res = []
let result = ''
if(k<=1){
    result = nums.join('->')
}else{
    while(nums.length>=k){
    let arr = nums.splice(0,k)
    let ar=[]
    for(let i=0;i<k;i++){
        let result = arr.shift()
        ar.unshift(result)
    }
    res.push(ar)
}

for(let i=0;i<res.length;i++){
    if(i==res.length-1&&nums.length==0){
            result+=res[i].join('-\>')
    }else{
            result+=res[i].join('-\>')+'->'
    }

}
let back = nums.join('->')
result = result+back
}

console.log(result)

发表于 2020-09-04 15:51:35 回复(0)
好难选还是独角兽头像 好难选还是独角兽 
//小渣渣直接用的list，输入输出很迷
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        LinkedList<String> list = new LinkedList<>();
        while(sc.hasNext()) {
            list.add(sc.next());
        }
        int k = new Integer(list.getLast());
        list.removeLast();
        list.removeLast();
        int len = list.size();
        int m = len/k;
        List<String> res = new LinkedList<>();
        for(int i=0; i<m*k;i+=k) {
            List<String> tmp = new LinkedList<>();
            tmp.addAll(list.subList(i, i+k));
            Collections.reverse(tmp);
            res.addAll(tmp);
        }
        res.addAll(list.subList(m*k, len));
        for(int i=0; i<res.size()-1;i++) {
            System.out.print(res.get(i)+"->");
        }
        System.out.print(res.get(len-1));
    }
}
发表于 2020-09-04 15:45:16 回复(0)
kevin_Wang333头像 kevin_Wang333 
//我是**
import java.util.*;
public class Main{
    public static void main(String args[]) {
            Scanner scanner = new Scanner(System.in);
        ArrayList<String> arraylist = new ArrayList<>();
        ArrayList<ArrayList<String>> arrayLists = new ArrayList<>();
        while (scanner.hasNext()) {
            arraylist.add(scanner.next());
        }
        int k = new Integer(arraylist.get(arraylist.size() - 1));
        arraylist.remove(arraylist.size() - 1);
        arraylist.remove(arraylist.size() - 1);
        int j = 0;
        for (int i = 0; i < arraylist.size() / k; i++) {
            int n = 0;
            ArrayList<String> array = new ArrayList<>();
            while (n < k) {
                array.add(arraylist.get(j));
                n++;
                j++;
            }
            Collections.reverse(array);
            arrayLists.add(array);
        }
        String str = "";
        for (int i = 0; i < arraylist.size() / k; i++) {
            for (int h = 0; h < k; h++) {
                str += arrayLists.get(i).get(h) + "->";
            }
        }

        for (int i = j; i < arraylist.size(); i++) {
            if (i == arraylist.size() - 1) {
                str += arraylist.get(i);
            } else {
                str += arraylist.get(i) + "->";
            }
        }
//末尾为 ->
        if (k == 1 || k == arraylist.size()) {
            StringBuilder stringBuilder = new StringBuilder(str);
            stringBuilder.delete(stringBuilder.length() - 2, stringBuilder.length());
            System.out.println(stringBuilder);
        } else {
            System.out.println(str);
        }
    }
}

编辑于 2020-09-04 13:45:36 回复(0)
C/C++
你占用了我昵称头像 你占用了我昵称
翻转链表的代码不多，处理这个输入输出的部分也写太多行了，有没有简单一点的处理“#”的方法啊😥 

#include <iostream>
#include <string>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(nullptr){}
    ListNode():val(0),next(nullptr){}
};

ListNode* re(ListNode* head,int k){
    // 下一组节点的首节点
    ListNode* next_head=head;
    for(int i=0;i<k;++i){
        // 该组长度小于k，不翻转，返回该组的首节点
        if(!next_head){
            return head;
        }
        next_head=next_head->next;
    }
    // 下一组节点翻转后的首节点
    ListNode* next_reverse_head=re(next_head,k);
    for(int i=0;i<k;++i){
        ListNode* nex=head->next;
        head->next=next_reverse_head;
        next_reverse_head=head;
        head=nex;
    }
    return next_reverse_head;
}

int main() {
    int k;
    int temp;
    cin >> temp;
    ListNode* head = new ListNode(temp);
    ListNode* cur = head;
    string t;
    while (cin >> t) {
        if (t=="#") {
            break;
        }        
        ListNode* nex = new ListNode(stoi(t));
        cur->next = nex;
        cur = cur->next;
    }   
    cin >> k;
    ListNode* res_head = re(head, k);
    string res;
    while (res_head) {
        res += to_string(res_head->val);
        if (res_head->next) {
            res += "->";
        }
        res_head = res_head->next;
    }
    cout << res << endl;
}
发表于 2020-08-13 16:02:25 回复(0)
Arith-SX头像 Arith-SX
'''
golang
''' 

package main

import (
    "fmt"
    "strconv"
)

func solve(a []int, k int) {
    length := len(a)
    for i := 0; i < length; {
        if i+k-1 < length {
            for m,n := i, i+k-1; m < n; m,n = m+1, n-1 {
                a[m], a[n] = a[n], a[m]
            }
        }
        i = i+k
    }
}

func main(){
    var nSlice = []int{}
    for {
        var temp = ""
        fmt.Scan(&temp)
        if temp == "#" {
            break
        } else {
            num, err := strconv.Atoi(temp)
            if err != nil {
                panic(err)
            } else {
                nSlice = append(nSlice, num)
            }
        }
    }
    var k = 0
    fmt.Scan(&k)
    solve(nSlice, k)
    for i, value := range nSlice {
        fmt.Print(value)
        if i != len(nSlice)-1 {
            fmt.Print("->")
        }
    }
}


发表于 2020-06-30 21:50:51 回复(0)
牛客820814220号头像 牛客820814220号
#python 3.5
arrList=input()[:-1].split()
k=int(input())
n=len(arrList)//k
foriinrange(1,n+1):
    arrList[k*(i-1):k*i]=arrList[k*(i-1):k*i][::-1]
print('->'.join(arrList))

发表于 2020-06-28 16:28:05 回复(0)
牛客763080691号头像 牛客763080691号

1，用栈逆序

2，栈分断输出到队列

3，剩余部分用队列尾部连接

发表于 2019-12-22 19:31:35 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 哔哩哔哩 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 数据分析工程师 数据挖掘工程师 测试开发工程师 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
15条回答 3499浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号