LeetCode刷题——旋转链表#61#Medium

LeetCode刷题——旋转链表#61#Medium

旋转链表的思路探讨与源码
     旋转链表的题目如下图，该题属于链表类型的题目，主要考察对于链表本身的理解和循环遍历链表技巧的优化使用。本文的题目作者想到2种方法，分别是闭环方法和快慢指针方法，其中闭环方法使用Java进行编写，而快慢指针方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用链表闭环的方法，首先判断链表是否为空或者是否只有一个元素，如果是就直接返回链表。然后进行参数初始化赋值，并且循环遍历链表得到链表长度，并且对链表长度和旋转参数进行取余数处理，如果余数是0那么就直接返回链表本身。否则就把最后一个节点连到链表的头部，然后遍历并寻找旋转后的末尾节点，找到后断开连接，并且最终返回链表。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode endNode = head;
        int num = 1;
        while (endNode.next != null) {
            num = num + 1;
            endNode = endNode.next;
        }
        int rt = k % num;
        if (rt == 0) {
            return head;
        }
        endNode.next = head;
        ListNode endNodeFake = head;
        int diff = num - rt;
        for (int jr = 1; jr < diff; jr++) {
            endNodeFake = endNodeFake.next;
        }
        ListNode startNodeFake = endNodeFake.next;
        endNodeFake.next = null;
        return startNodeFake;
    }
}

    显然，我们看到闭环链表的方法效率不错，同时还可以使用快慢指针的方法进行处理，首先判断链表的长度，如果是0或者能被旋转次数整除就直接返回链表本身。然后进行参数初始化处理，将快慢指针都指向开始的链表头，让快指针先走旋转次数与链表长度取余数的步数，然后快慢指针开始一起遍历，直到快指针走到链表的尾部，这个时候的慢指针的所在位置就是尾部位置，然后进行链表的参数赋值即可，最终返回链表结果。所以按照这个思路就可以解决，下面是Python代码部分：

#喷火龙与水箭龟
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        test = head
        num = 0
        while test:
            num = num + 1
            test = test.next
        if num == 0 or (k % num) == 0:
            return head
        a = head
        b = head
        yu = k % num
        for jr in range(yu):
            a = a.next
        while a.next:
            a = a.next
            b = b.next
        a.next = head
        head = b.next
        b.next = None
        return head

    从结果来说Java版本的闭环链表方法的效率不错，而Python版本的快慢指针方法的速度一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。