61-旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 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

---

解法

核心思想：根据规律找出旋转点，再重新构建链表。

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if head == None or head.next == None or k == 0:
            return head
        p = head  # 指针
        len_ListLink = 1
        # 遍历计算链表长度
        while p.next:
            len_ListLink += 1
            p = p.next
        # 找到原表尾的位置
        rear = p
        # 转折点位置
        t = len_ListLink - (k % len_ListLink)
        if t == len_ListLink:
            return head
        p = head  # 第二次遍历指针
        while t > 1:
            t -= 1
            p = p.next
        newRear = p
        newHead = p.next
        # 重新构建链表
        newRear.next = None
        rear.next = head
        return newHead

另外解的思想：将链表转换为list，排列后在生成链表

---

相关信息

LeetCode：Discussion | Solution