每日算法-旋转链表.md

每日算法

难度 - > 中等

日期 - > 2021年3月27日

开始时间 - > 21:07

结束时间 - > 22:01

所用时间 - > 58分钟

执行用时 - > 00 ms

内存消耗 - > 38.2 MB

题目

中文

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

**输入**：head = [1,2,3,4,5], k = 2
**输出**：[4,5,1,2,3]

实例 2:

**输入**：head = [0,1,2], k = 4
**输出**：[2,0,1]

提示：

- 链表中节点的数目在范围 `[0, 500]` 内

- `-100 <= Node.val <= 100`

- `0 <= k <= 2 * 109`

英文

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

**Input**: head = [1,2,3,4,5], k = 2
**Output**: [4,5,1,2,3]

Example 2:

**Input**: head = [0,1,2], k = 4
**Output**: [2,0,1]

Constraints:

- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 109

代码

/**
 * 旋转链表
 * Rotate List
 * @author HCY
 * @since 2021/3/27 下午9:21
*/
public class Solution {
    /**
     * 已经反转的次数
     */
    private int count = 0;
    private ListNode head;

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        this.head = head;
        helper(head, k, 1);
        return this.head;
    }

    /**
     *
     * @author HCY
     * @since 2021/3/27 下午9:52
     * @param node: 链表
     * @param k: 反转次数
     * @param count: 已经反转的次数
     * @return void
    */
    private void helper(ListNode node, int k, int count) {
        if(node.next == null) {
            node.next = head;
            this.count = count;
        } else {
            helper(node.next, k, count + 1);
        }

        if(count == this.count - k % this.count) {
            this.head = node.next;
            node.next = null;
        }
    }

}