61:旋转链表
程序员文章站
2022-05-20 13:46:13
...
问题描述
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例
输入: 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
输入: 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比链表的长度大的话,那么需要模一下
因为转一圈的话相当于没转
断链的位置就是从后往前数k个元素
记录一个旋转后的真实的tail,
记录一个当前的tail
然后返回旋转后真实的head即可。
AC代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
'''
这题就是在某个位置断链,然后重组即可。
我们发现如果k比链表的长度大的话,那么需要模一下
因为转一圈的话相当于没转
断链的位置就是从后往前数k个元素
记录一个旋转后的真实的tail,
记录一个当前的tail
然后返回旋转后真实的head即可。
'''
def rotateRight(self, head, k: int):
if not head:
return head
length = self.getLengh(head)
k %= length
if k == 0:
return head
temp = head # 让temp去跑,head指向原来的head
count = 0
true_head = tail = true_tail = None
while temp:
if count == length - k:
true_head = temp
elif count == length -k - 1:
true_tail = temp
count += 1
tail = temp
temp = temp.next
tail.next = head
true_tail.next = None # 防止成环
return true_head
def getLengh(self,head):
l = head
count = 0
while l:
l = l.next
count += 1
return count