leetcode 【 Reverse Nodes in k-Group 】 python 实现

浏览数：32 / 时间：2015年06月08日

原题：

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

代码：oj测试通过 Runtime: 125 ms

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     # @param head, a ListNode
 9     # @param k, an integer
10     # @return a ListNode
11     def reverseKGroup(self, head, k):
12         if head is None or head.next is None or k<2:
13             return head
14         
15         dummyhead = ListNode(0)
16         dummyhead.next = head
17         
18         slow = dummyhead
19         fast = dummyhead
20         
21         while 1:
22             sign = 0
23             for i in range(k):
24                 if fast.next is not None:
25                     fast = fast.next
26                 else:
27                     sign = 1
28                     break
29             if sign == 1 :
30                 break
31             else:
32                 curr = slow.next
33                 for i in range(k-1):
34                     tmp = curr.next
35                     curr.next = tmp.next
36                     tmp.next = slow.next
37                     slow.next = tmp
38                 slow = curr
39                 fast = curr
40         
41         return dummyhead.next