leetcode 【 Reverse Linked List II 】 python 实现

hawl

　　题目：
　　Reverse a linked list from position m to n. Do it in-place and in one-pass.
　　For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
　　return 1->4->3->2->5->NULL.
　　Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
　　
　　代码：oj测试通过 Runtime: 65 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 m, an integer
10     # @param n, an integer
11     # @return a ListNode
12     def reverseBetween(self, head, m, n):
13         if head is None or head.next is None:
14             return head
15         dummyhead = ListNode(0)
16         dummyhead.next = head
17         
18         p = dummyhead
19         
20         for i in range(m-1):
21             p = p.next
22         
23         curr = p.next
24         for i in range(n-m):
25             tmp = curr.next
26             curr.next = tmp.next
27             tmp.next = p.next
28             p.next = tmp
29            
30         return dummyhead.next
　　
　　思路：
　　不妨拿出四本书，摞成一摞（自上而下为 A B C D），要让这四本书的位置完全颠倒过来（即自上而下为 D C B A）：
　　盯住书A，每次操作把A下面的那本书放到最上面
　　初始位置：自上而下为 A B C B
　　第一次操作后：自上而下为 B A C D
　　第二次操作后：自上而下为 C B A D
　　第三次操作后：自上而下为 D C B A
　　小白觉得四本书的例子，貌似可以更有助于解释代码，欢迎大侠拍砖指导。