LeetCode 0061 - Rotate List
# Hints
- 链表
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a linked list, rotate the list to the right by places, where is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
# 题意
给定一个链表和一个非负整数 ,要求将链表向右循环移动 个单位。
# 题解
设链表的长度为 。若 ,则问题等价于将链表向右循环移动 个单位。否则,我们只需将链表从左往右数的前 个节点和后 个节点分割为两个链表 和 ,然后将 的左端与 的右端相接即可。
# AC代码
/**
* 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) {
// 特判
if (head == nullptr) {
return head;
}
// 初始化
int n = get_list_length(head);
k = k % n;
// 特判
if (k == 0) {
return head;
}
// 获取左右链表
ListNode * tail = head;
for (int i = 1; i <= n - k - 1; i ++) {
tail = tail->next;
}
ListNode * nhead = tail->next;
ListNode * ntail = nhead;
while (ntail->next != nullptr) {
ntail = ntail->next;
}
// 旋转
tail->next = nullptr;
ntail->next = head;
// 返回
return nhead;
}
// 获取链表长度
int get_list_length(ListNode * head) {
int len = 0;
ListNode * p = head;
while (p != nullptr) {
len ++;
p = p->next;
}
return len;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01