[LeetCode]题解(python):061-Rotate list


题目来源


https://leetcode.com/problems/rotate-list/

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.


题意分析


Input:a list of node

Output:a list of node shift to right

Conditions:链表右移


题目思路


总体思路是链表右移,关键是右移k可能大于实际长度,所以先遍历一次求长度,然后再求模得到真正右移数量

PS:对于链表操作,每次在前面添加一个节点这个方法很好用,特别注重边界条件

PS2:尽量用xrange代替range


AC代码(Python)


 __author__ = 'YE'

 # 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 k == 0 or head == None:
return head addFirst = ListNode(0)
addFirst.next = head
# move variable
p = addFirst
#the length of list
count = 0
while p.next != None:
p = p.next
count += 1
p.next = addFirst.next
#the real step to shift right
step = count - (k % count)
p = addFirst.next
for i in xrange(1, step):
p = p.next
head = p.next
p.next = None return head
上一篇:[原]性能优化之Hibernate缓存讲解、应用和调优


下一篇:洛谷P1605 迷宫【dfs】