【LeetCode with Python】 61. Rotate List

题目

原题页面：https://leetcode.com/problems/rotate-list/
本文地址：http://leetcode.xnerv.wang/rotate-list/
题目类型：Linked List, Two Pointers
难度评价：Medium
类似题目：(E) Rotate Array

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

分析

这类链表倒置，或链表局部倒置的题目，都是大学数据结构课程的日常题目。一般要注意三点：

1. 在必要的head/tail处设置指针，便于操作；
   
2. 注意当节点数n为0、1、2等时的特殊情况下的处理，记得检查指针是否为None；
   
3. 有时候head或tail需要特殊处理，此时可以通过增加一个new_head或new_tail，使得head或tail可以被当成普通节点来处理。
   

代码

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def rotateRight(self, head, k):
        if None == head or None == head.next:
            return head
        cur_head = head
        cur = head
        while k > 0:
            cur = cur.next
            if None == cur:
                return head
            k -= 1
        cur_tail = cur
        cur_head = cur.next
        if None == cur_head:
            return head
        cur = cur_head
        while None != cur.next:
            cur = cur.next
        cur.next = head
        cur_tail.next = None
        return cur_head