【3.27】LeetCode每日一题· 旋转链表

2021年03月27日 13时31分

标签： LeetCode 链表

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

#### 示例1
![](https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg)
```
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
```

#### 示例2
![](https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg)
```
输入：head = [0,1,2], k = 4
输出：[2,0,1]
```

#### 提示
```
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/rotate-list/ "题目链接")

## 解题思路
可以先将链表首尾相连，成为一个循环链表。设`len`为链表长度。

如果将循环链表中，原链表**头节点`head`后的第`len-1-k `个节点的后一个节点**置为头节点，而**头节点`head`后的第`len-1-k `个节点**置为尾节点，那么所获得的链表，即为将链表右移`k`次所得到的新链表。

除此以外，观察测试用例2，链表右移`k`次和右移`k % len`等价。

因此模拟上述操作即可。

### 代码
```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int len = 0;
        ListNode* curr = head, *end = nullptr, *res = nullptr;
        while(curr){
            len++;
            if(!curr->next) end = curr;
            curr = curr->next;
        }
        if(len == 0) return head;
        k %= len;
        end->next = head;
        curr = head;
        for(int i = 0; i < len-1-k; i++){
           curr = curr->next;
        }
        res = curr->next;
        curr->next = nullptr;
        return res;
    }
};
```

## 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了82.17%的用户
> 内存消耗：11.4 MB，在所有 C++提交中击败了81.61%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.27】LeetCode每日一题· 旋转链表

所有评论

暂无评论

新增评论