61. 旋转链表
解题思路1
将各节点存储到列表中，对列表切片+拼接实现循环右移，再重新生成链表
代码1
# 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: ListNode, k: int) -> ListNode:
if not head:
return None
stack = [head]
head = head.next
while head:
stack.append(head)
head = head.next
transLength = k % len(stack)
stack = stack[-transLength:] + stack[:-transLength]
stack.append(None)
for i in range(len(stack)-1):
stack[-i-2].next = stack[-i-1]
return stack[0]
解题思路2
求链表长度；
找出倒数第 k+1 个节点；
链表重整：将链表的倒数第 k+1 个节点和倒数第 k 个节点断开，并把后半部分拼接到链表的头部。
代码2
# 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, k):
if not head or not head.next: return head
# 求链表长度
_len = 0
cur = head
while cur:
_len += 1
cur = cur.next
# 对长度取模
k %= _len
if k == 0: return head
# 让 fast 先向后走 k 步
fast, slow = head, head
while k:
fast = fast.next
k -= 1
# 此时 slow 和 fast 之间的距离是 k；fast 指向第 k+1 个节点
# 当 fast.next 为空时，fast 指向链表最后一个节点，slow 指向倒数第 k + 1 个节点
while fast.next:
fast = fast.next
slow = slow.next
# newHead 是倒数第 k 个节点，即新链表的头
newHead = slow.next
# 让倒数第 k + 1 个节点 和 倒数第 k 个节点断开
slow.next = None
# 让最后一个节点指向原始链表的头
fast.next = head
return newHead
版权声明：本文为tensorzhang原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。