LeetCode61-旋转链表

明天就要回家了

说实话，心里没点波澜

一个学期都没有回家看看了

但归家之心却并不怎么强烈

也不知为何

但回家了，还有一堆事在等着我

充实

---

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

思路：

这一题我写了两种方法，首先介绍最容易想到的方法吧。第一种方法其实很简单，就是先把给定链表节点对应的value值全部用一个数组list来存储，题目要求：将链表每个节点向右移动 k 个位置，其实就相当于是把数组list中最后一个值依次放到数组的第一个位置，循环k次。最后将新的数组List中的值依次赋值给一链表返回即可。

代码如下：

class Solution(object):
    # 本题的主要思路就是：不断的将链表对应值的数组中的最后一个数插入到数组的第一个位置，其他元素相应后移
    # 这儿有个地方需要注意：k值最好是取k%len(head)[链表节点的个数]因为当k值过大时很多重复操作是没必要的
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # 该数组专门用来保存链表对应的值
        head_list = []
        # 遍历链表，分别取出对应节点的值
        while head is not None:
            head_list.append(head.val)
            head = head.next
        # 如果链表是空链表，直接返回空数组
        if len(head_list) == 0:
            return []
        # 对k进行预处理，避免重复操作
        k = k % len(head_list)
        # 将head_list数组里的最后一个数移到第一位，其他元素相应右移一位，重复k次
        for indice in range(k):
            last_num = head_list[-1]
            head_list.insert(0, last_num)
            head_list.pop()
        # 将得到的新head_list数组里的元素赋值给一个新的链表返回
        new_head = ListNode(0)
        new_head_copy = new_head
        for index in head_list:
            node = ListNode(index)
            new_head_copy.next = node
            new_head_copy = new_head_copy.next
        return new_head.next


if __name__ == "__main__":
    node_list = [1, 2, 3]
    head = ListNode(0)
    head_copy = head
    for index in node_list:
        node = ListNode(index)
        head_copy.next = node
        head_copy = head_copy.next
    k = 200000000
    final_node = Solution().rotateRight(head.next, k)
    print(final_node)

执行效率一般，在50%左右。

还有一种方法就是比较巧了，上一种方法是借助了一数组来存储链表节点的值，这个其实占用了很大的存储空间，这种方法省略了这一步，直接对给定链表做手脚。核心思路就是：将原线性非循环链表首尾节点相连，转化为循环链表，因为将链表每个节点向右移动 k 个位置后，该链表中节点的值不会改变，所以我们只需找到相应的头结点和尾节点即可表示出新的链表。可参考下图：

 

具体代码如下：

class Solution(object):
    # 本题的主要思路就是：将该链表的尾节点指向头结点，构造循环链表。然后定义一个指针，指向最终的头结点
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None:
            return None
        head_length = 1
        # 获取head链表的尾节点
        loop_node = head
        while loop_node.next is not None:
            loop_node = loop_node.next
            head_length += 1
        # 将该链表的尾节点指向头结点，构造循环链表
        loop_node.next = head
        # 对k进行预处理，避免重复操作
        k = head_length - k % head_length
        for index in range(k):
            head = head.next
            loop_node = loop_node.next
        loop_node.next = None
        return head


if __name__ == "__main__":
    node_list = [1, 2, 3, 4, 5]
    head = ListNode(0)
    head_copy = head
    for index in node_list:
        node = ListNode(index)
        head_copy.next = node
        head_copy = head_copy.next
    k = 3
    final_node = Solution().rotateRight(head.next, k)
    print(final_node)

执行效率可以，在90%左右。