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

题目描述

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围： 0≤n≤2000 ， 1≤k≤2000 ，链表中每个元素都满足0≤val≤1000
要求空间复杂度 O(1)，时间复杂度 O(n)

例如：

给定的链表是 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}

示例2

输入：

{},1

返回值：

{}

解题思路

解法1 利用哑结点

1.使用哑结点，遍历Node，得到num，这样我们知道了有多少个k

2.开始遍历，对于大于等于k的时候，直接采用头插法，一直插入，但是记得头插完成一轮之后，记得需要将节点移动到末尾

3.直到num小于k的时候，开始使用尾插法

4.此时哑结点的下一节点，即为所求结果

解法2 空间复杂度为O（1）的解法

使用哑结点的解法，时间复杂度和空间复杂度都是O（n），题目要求，空间复杂度需要为O（1）

暂时没有想到

实践代码

解法 1 代码

public class Solution {
    /**
     * 
     * @param head
     *            ListNode类
     * @param k
     *            int整型
     * @return ListNode类 @空间复杂度O(n)，时间复杂度O(n)
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        int num = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            num++;
        }


        ListNode result = new ListNode(1);
        ListNode res = result;
        while (num > 0) {
            if (num >= k) {
                //满k的元素，头插法
                for (int i = 0; i < k; i++) {
                    ListNode node = res.next;
                    res.next = new ListNode(head.val);
                    res.next.next = node;
                    head = head.next;
                    num--;
                }
                //走到下一个位置
                for (int i = 0; i < k; i++) {
                    res = res.next;
                }
            } else {
                //不满k的元素，尾插法
                while (head != null) {
                    res.next = new ListNode(head.val);
                    res = res.next;
                    head = head.next;
                    num--;
                }
            }
        }
        return result.next;
    }
}

解法2 代码

`暂时没有想到`