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

61. 旋转链表

原文：https://www.cnblogs.com/tensorzhang/p/14585113.html