专栏首页InvQ的专栏递归解决k个一组的链表节点翻转问题

递归解决k个一组的链表节点翻转问题

problem

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5

当 k = 2 时,应当返回: 2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5

说明:

你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

原文链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group

solution

1、找到待翻转的k个节点,若剩余数量小于 k 的话,则不需要反转,因此直接返回待翻转部分的头结点即可。 2、对其进行翻转。并返回翻转后的头结点,翻转为左闭右开区间,所以本轮操作的尾结点其实就是下一轮操作的头结点。 3、对下一轮 k 个节点也进行翻转操作。 4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。

大致流程入下图:

head = tail 返回pre节点,也就是值为3的节点作为newHead 。再次递归即可。

public class SwapKGroup {
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话,则不需要反转。
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);

        return newHead;
    }

    /*
    左闭右开区间
     */
    private static ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;

    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = new ListNode(5);
        reverseKGroup(listNode1,3);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 写一个函数,2 个参数,1 个字符串,1 个字节数,返回截取的字符串,要 求字符串中的中文不能出现乱码

    写一个函数,2 个参数,1 个字符串,1 个字节数,返回截取的字符串,要

    MickyInvQ
  • 我们在 web 应用开发过程中经常遇到输出某种编码的字符,如 iso8859-1 等,如何输出一个某种编码的字符串?

    public String translate(String str){//对传入的str字符串进行转换

    MickyInvQ
  • 走访 Linked List 时考虑进位

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

    MickyInvQ
  • LintCode 重排链表题目分析代码

    样例 给出链表 1->2->3->4->null,重新排列后为1->4->2->3->null。

    desperate633
  • LintCode 翻转链表 II题目代码

    desperate633
  • 每日一题-反转链表

    输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

    程序员小王
  • LeetCode155|移除链表元素

    一个是基于哨兵节点的方式进行解决,另一个是基于java集合的方式来做,本质上还是一样的

    码农王同学
  • LeetCode142|移除重复节点

    对于这道题而言,理解哨兵节点的设置,以及LinkedHashSet的作用就可以了。

    码农王同学
  • LeetCode77|排序链表

    有的时候自己写完整道题之后,确实不知道给你们说什么了,我觉得目前我输出的内容都是常规思路题,所以你懂吧,看懂代码的可以自己单独写写就可以了,具体的解题思路真的不...

    码农王同学
  • LeetCode18|排序链表

    码农王同学

扫码关注云+社区

领取腾讯云代金券