python实现leetcode之61. 旋转链表

解题思路

快慢指针

1. 快指针先走k步
2. 快慢指针一起走知道快指针到尾部，慢指针就是新的头
3. 将老的尾接新的头，就是ans

61. 旋转链表

代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head: return head
        length = len_of_chain(head)
        k %= length
        if not k: return head
        fast = head
        while k:
            fast = fast.next
            k -= 1
        p1 = ans = head
        p2 = fast
        while fast:
            p1 = ans
            ans = ans.next
            p2 = fast
            fast = fast.next
        p1.next = None
        p2.next = head
        return ans


def len_of_chain(head):
    if not head: return 0
    return 1 + len_of_chain(head.next)