61.旋转链表
题目描述
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
思路
方法一： 闭合为环
记给定链表的长度为 n，注意到当向右移动的次数 k≥n 时，我们仅需要向右移动 k mod n 次即可。因为每 n 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n−1)−(k mod n) 个节点（从 0 开始计数）。
这样，我们可以先将给定的链表连接成环，然后将指定位置断开。
具体代码中，我们首先计算出链表的长度 n，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 (n−1)−(k mod n) 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。
方法二： 将后k个节点移到前n-k个节点之前（n为链表长度）
特别地，当链表长度不大于 1，或者 k 为 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
# 如果链表为空直接返回head
# 如果右旋转的次数为0直接返回head
if head is None or head.next is None or k == 0 :
return head
# 统计head链表的长度
p1 = head
count = 0
while p1:
count += 1
p1 = p1.next
# 如果链表只有一个节点，直接返回head
# 如果右旋转次数除以链表长度的余数为0,直接返回head
if k % count == 0:
return head
i = 0
p2 = head
k = k % count # 去掉整圈的旋转
while i < count - k - 1: # 找到后k个节点的前一个节点
p2 = p2.next
i += 1
second = p2.next # second为后k个节点组成的链表
p2.next = None # 将前count - k个节点的最后一个节点的next值置空
p3 = second
while p3.next is not None: # 找到后k个节点组成的链表的最后一个节点
p3 = p3.next
p3.next = head # 将后k个节点组成的链表与前count-k个节点组成的链表连接起来
return second
def rotateRight1(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k == 0 or not head or not head.next:
return head
# 求链表长度
n = 1
cur = head
while cur.next:
cur = cur.next
n += 1
add = n - k % n
if add == n:
return head
# 链表闭合成环
cur.next = head
while add:
cur = cur.next
add -= 1
ret = cur.next
cur.next = None # 将闭合为环的链表断开
return ret
def create_linked_list(self, list):
"""根据list中的所有元素构建单链表"""
l = ListNode() # 单链表头节点
r = l # 起始尾指针r指向头节点
for e in list:
node = ListNode(e)
r.next = node
r = r.next
return l.next
def print_linked_list(self, linked_list) -> None:
"""
打印单链表中的所有元素
:param linked_list: 单链表
:return: 无
"""
print("----------------------------------------")
pointer = linked_list
while pointer is not None:
print(pointer.val)
pointer = pointer.next
if __name__ == "__main__":
slt = Solution()
linked_list = slt.create_linked_list([1, 2])
slt.print_linked_list(linked_list)
rotated_linked_list = slt.rotateRight1(linked_list, 2)
slt.print_linked_list(rotated_linked_list)