1. 题目描述
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给你一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置。
示例 1：
1
2
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
1
2
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：
- 链表中节点的数目在范围
[0, 500]内 -100 <= Node.val <= 1000 <= k <= 2 * 10^9
2. 题解
科研没有进展，也就只好刷题了！
题目 将链表每个节点向右移动k个位置，其实可以等价为 把链表末尾的k个节点接到原链表的头节点前。但也存在一个问题，k的大小是可能大于链表节点个数的，当大于链表节点个数时，需要进行取余计算，如下图所示（橙色覆盖的节点表示被移动到头节点的末尾节点）： 
因此需要知道如下信息：
- 链表中节点的个数
m - 变换后的
k值，即_k = k % m - 链表末尾的
_k个节点的位置
因此，我的第一反应就是用 栈 进行实现。遍历链表，节点入栈同时进行节点计数得到m；到达链尾，计算_k = k % m；然后出栈_k个节点，并进行指针重设。
算法流程：
- 在原本的链表头部，新增一个头节点，方便后续操作，并创建两个指针（头指针
head_ptr，尾指针tail_ptr）均指向这个新的头节点； - 创建一个栈用于存放链表节点，通过尾指针遍历链表并把遍历到的节点入栈，同时进行节点计数；
- 链表遍历完成之后得到链表长度，计算真正需要移动到头部的节点个数
_k； - 出栈
_k个节点，此时栈中最后一个节点（令其为stack[-1]）应设置为尾节点，而其原本的下一个节点应被设置为头节点，并将遍历得到的尾指针tail_ptr所指节点链接到head_ptr指向的下一个节点。操作如下：
1
2
3
4
5
6
7
8
9
# 在进行指针操作之前，head_ptr指向新增的头节点，tail_ptr指向原链表的尾节点，
# stack[-1]为应移动到头部的_k个节点的前一个节点
# stack[-1]的下一个节点应被设置为新的头节点new_head，并作为函数返回值
new_head = stack[-1].next
# stack[-1]本身应被设置为新的尾节点，因此其next应被重置为null
stack[-1].next = tail_ptr.next
# 原链表的尾节点应链接到原链表的头节点之前
tail_ptr.next = unk_head.next
3. 代码实现
Python实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 特殊情况，无节点，直接返回
if not head:
return head
unk_head = ListNode(0, head)
head_ptr = unk_head
tail_ptr = unk_head
cnt = 0
stack_list = []
# 入栈
while tail_ptr.next != None:
tail_ptr = tail_ptr.next
stack_list.append(tail_ptr)
cnt += 1
_k = k % cnt
# 特殊情况，_k=0，无需操作，直接返回
if _k == 0:
return head
# 出栈
for i in range(_k):
stack_list.pop()
# 指针重设
new_head = stack_list[-1].next
stack_list[-1].next = tail_ptr.next
tail_ptr.next = unk_head.next
return new_head