首页 > 试题广场 >

将单链表的每K个节点之间逆序

[编程题]将单链表的每K个节点之间逆序

热度指数：2190 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个单链表，实现一个调整单链表的函数，使得每 K 个节点之间的值逆序，如果最后不够 K 个节点一组，则不调整最后几个节点。

输入描述:

第一行一个整数 n，n 表示单链表的节点数量。

第二行 n 个整数 val 表示链表的各个节点的值。

第三行一个整数 K。

输出描述:

在给定的函数内返回链表的头指针。

示例1

输入

5
1 2 3 4 5
3

输出

3 2 1 4 5

备注:

算法知识视频讲解

Java

小白小白啦

力扣上面的提交很快给结果通过，这个牛客判题系统，一会85%，再提交75%我都服了，并且判题时间很长，能不能把判题系统稍微做的好一点。
把我力扣写的题解复制过来，刷了十来道链表题了，基本上都能用递归写出来，之前是很害怕，感觉递归好难写。就遵循一句话就可以用递归都写出来。这句话分为三步
1、找到终止条件
2、假设递归函数已经将后面的都完成了
3、处理第一个情况。
在这个题目中是这么处理
1、递归终止条件是head为null或者剩余节点数量小于k，那就直接返回
2、如果链表为1->2->3->4->5->null，k为2，那么假设3->4->5经过递归函数以及完成了翻转
3、接下来处理第一个情况，也就是1->2。

import java.util.Scanner;
/**
 * @Author fgf
 * @create 2020/3/5 12:44
 * 将单链表的每K个节点之间逆序
 */
class Node {
    public int val;
    public Node next;
    public Node(int data){
        this.val = data;
    }
}
public class Main {
    public static Node reverseKGroup(Node head, int k){
        if(head == null)
            return head;
        int m = k;
        ListNode cur = head;
        while(cur != null && --m >= 1)
            cur = cur.next;
        if(m >= 1)
            return head; //剩余节点不到k个，直接返回
        ListNode pre = reverseKGroup(cur.next, k);//假设3->4->5->null已经完成，已经变成4->3->5->null
        cur.next = null; //处理第一种情况，当前节点为2，要把2的next设置为null,作为终止条件
        cur = head;//从head也就是1开始处理
        //将head到cur进行翻转
        while(cur != null){
            ListNode  = cur.next; //记录下一个节点，也就是2
            cur.next = pre;//将1指向pre也就是前一个节点，也就是前面的4->3->5->null
            pre = cur;//将pre设置为1
            cur = next;//将cur设置为2
        }
        return pre;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        Node head = new Node(-1);
        Node cur = head;
        for(int i=0; i<count; i++){
            cur.next = new Node(scanner.nextInt());
            cur = cur.next;
        }
        int k = scanner.nextInt();
        Node result= reverseKGroup(head.next, k);
        while(result!=null){
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

编辑于 2020-03-09 12:03:27 回复(3)

Java

pein531

利用链表天然的递归性质：(1) 前半段如果凑足了k个节点就进行逆序，否则直接返回头结点；(2) 后半段继续这个过程去凑k个节点；(3) 前后半段处理完成后将链表接起来。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int k = Integer.parseInt(br.readLine());
        ListNode head = new ListNode(Integer.parseInt(strArr[0]));
        ListNode cur = head;
        for(int i = 1; i < strArr.length; i++){
            cur.next = new ListNode(Integer.parseInt(strArr[i]));
            cur = cur.next;
        }
        head = reverseKGroups(head, k);
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    private static ListNode reverseKGroups(ListNode head, int k) {
        ListNode cur = head;
        for(int i = 1; i < k && cur != null; i++)
            cur = cur.next;
        if(cur == null) return head;      // 不足k个了，直接返回头节点
        ListNode temp = cur.next;
        cur.next = null;
        ListNode newHead = reverseList(head);      // 前面一段逆序
        head.next = reverseKGroups(temp, k);       // 后面继续进行k个一组的反转
        return newHead;
    }
    
    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

发表于 2021-11-17 21:58:38 回复(0)

无心2019

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list()
{
    int val, n;
    scanf("%d", &n);
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * reverse_knode(list_node * head1, int K)
{
    //////在下面完成代码
    if (K < 2)
        return head1;
    list_node *start = nullptr;
    list_node *pre = nullptr;
    list_node *cur = head1;
    list_node *next = nullptr;
    int count = 1;
    while (cur != nullptr)
    {
        next = cur->next;
        if (count == K)
        {
            start = pre == nullptr ? head1 : pre->next;
            head1 = pre == nullptr ? cur : head1;
            list_node *n1 = start;
            list_node *n2 = start->next;
            list_node *n3 = nullptr;
            while (n2 != next)
            {
                n3 = n2->next;
                n2->next = n1;
                n1 = n2;
                n2 = n3;
            }
            if (pre != nullptr)
                pre->next = cur;
            start->next = next;
            pre = start;
            count = 0;
        }
        count++;
        cur = next;
    }
    return head1;
}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    int K;
    scanf("%d", &K);
    list_node * new_head = reverse_knode(head, K);
    print_list(new_head);
    return 0;
}

发表于 2019-09-20 17:49:04 回复(0)

牛客114912041号

a,b,c=int(input()),input().split(),int(input())

m=0

d=[]

while m+c <=len(b):

d.append(" ".join(b[m:(m+c)][::-1])+" ")

m+=c

p=""

for i in d:

p +=i

print(p+" ".join(b[m:]))

发表于 2022-11-20 17:23:56 回复(0)

牛娃牛娃

list_node * reverselist(list_node *start,list_node *end){
    list_node *cur =start;
    list_node *pre =end;
    list_node *temp;
    while(cur!=end){
        temp =cur->next;
        cur->next =pre;
        pre=cur;
        cur =temp;
    }
    return pre;
}

list_node * reverse_knode(list_node * head1, int K)
{
    //////在下面完成代码
    if(head1==nullptr)return nullptr;
    list_node *a =head1;
    list_node *b =head1;
    //a原地不动 b走k个  形成a---b区间
    for(int i=0;i<K;i++){
        if(b!=nullptr){
            b=b->next;
        }else{
            return head1;
        }
    }
    //翻转ab区间 更新新的区间b--k
    list_node *newhead =reverselist(a,b);
    a->next =reverse_knode(b,K);
    return newhead;

}

发表于 2022-05-24 19:08:20 回复(0)

p_string

思路：每K个节点进行反转，不足K也进行反转；最后再处理不足K个的情况

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] rawInput = br.readLine().trim().split(" ");
        int k = Integer.parseInt(br.readLine().trim());
        
        // 构建链表
        Node head = buildLinkedList(rawInput);
        // 按要求逆序链表
        head = reverseKList(head, k);
        // 打印链表
        printLinkedList(head);
        br.close();
    }
    
    private static Node reverseKList(Node head, int k) {
        if (null == head || k <= 1) {
            return head;
        }
        
        Node newHead = null, curNode = head, preNode = null, next = null;
        int cnt = k;
        Node lastStartNode = head;
        Node nextCurNode = head;
        while (null != curNode) {
            if (cnt-- > 0) {
                // 正常反转
                next = curNode.next;
                curNode.next = preNode;
                preNode = curNode;
                curNode = next;
            } else {
                cnt = k;
                if (null == newHead) {
                    newHead = preNode;
                    lastStartNode = head;
                } else {
                    lastStartNode.next = preNode;
                    lastStartNode = nextCurNode;
                }
                nextCurNode = curNode;
                preNode = null;
            }
        }
        
        if (cnt == 0) {
            lastStartNode.next = preNode;
            return newHead;
        }
        
        // 最后不够k个节点了
        curNode = preNode;
        Node tmpPreNode = null;
        while (null != curNode) {
            next = curNode.next;
            curNode.next = tmpPreNode;
            tmpPreNode = curNode;
            curNode = next;
        }
        lastStartNode.next = tmpPreNode;
        
        return newHead;
    }
    
    // 打印链表
    private static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (null != head) {
            sb.append(head.value).append(" ");
            head = head.next;
        }
        System.out.print(sb.toString().trim());
    }
    
    private static Node buildLinkedList(String[] rawInput) {
        Node head = null, curNode = null;
        
        for (int i = 0; i < rawInput.length; i++) {
            Node tmpNode = new Node(Integer.parseInt(rawInput[i]));
            if (null == head) {
                head = tmpNode;
            } else {
                curNode.next = tmpNode;
            }
            curNode = tmpNode;
        }
        
        return head;
    }
}

class Node {
    public int value;
    public Node next;
    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

发表于 2020-08-02 23:25:03 回复(0)