2021/3/19 链表中的节点每k个一组翻转

链表中的节点每k个一组翻转

http://www.nowcoder.com/questionTerminal/b49c3dc907814e9bbfa8437c251b028e

题目描述

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
要求空间复杂度 O(1)
例如:
给定的链表是1→2→3→4→5
对于 k=2, 你应该返回 2→1→4→3→5
对于 k=3, 你应该返回 3→2→1→4→5

示例1

输入

{1,2,3,4,5},2

返回值

{2,1,4,3,5}

解题思路

使用递归法,去解决每 k 个部分的反转。
图片说明

图片说明
从上面图例可以看出,每次反转结束之后,pre 指向的位置是上一次反转结束时最后一个元素的下一个元素(即 1 连接着 4)。我们可以利用这一点做一个递归。

Java代码实现

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        if (head == null || k <= 1) return head;
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        // 遍历链表,如果遍历到 null,说明长度不够,返回 head 即可
        for (int i = 0; i < k; ++i) {
            if (cur == null) return head;
            cur = cur.next;
        }
        cur = head;    // 重新设置回头部
        // 从 head 开始到后面 k 个元素的链表反转操作
        for (int i = 0; i < k; ++i) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        // head.next 就是下一次反转的 prev
        head.next = reverseKGroup(next, k);
        return prev;
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 07:39
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议