木又同学2020年第27篇解题报告
leetcode第61题:旋转链表
https://leetcode-cn.com/problems/rotate-list
【题目】
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
【思路】
这道题细节太多了,方法应该都差不多,需要注意的是,k是有可能大于链表长度的。
我们首先遍历链表,得到链表长度;接着遍历链表找到真实旋转位置;最后进行旋转。
【代码】
python版本
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k == 0 or head is None:
return head
# 统计节点个数
p = head
count = 1
while p.next is not None:
p = p.next
count += 1
# k对count取余
k %= count
if k == 0:
return head
# 找到旋转位置
count = count - k - 1
q = head
while count > 0:
count -= 1
q = q.next
# 旋转
p.next = head
head = q.next
q.next = None
return head