首页 > 代码库 > leetcode 【 Reverse Linked List II 】 python 实现

leetcode 【 Reverse Linked List II 】 python 实现

题目

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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn 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 integer10     # @param n, an integer11     # @return a ListNode12     def reverseBetween(self, head, m, n):13         if head is None or head.next is None:14             return head15         dummyhead = ListNode(0)16         dummyhead.next = head17         18         p = dummyhead19         20         for i in range(m-1):21             p = p.next22         23         curr = p.next24         for i in range(n-m):25             tmp = curr.next26             curr.next = tmp.next27             tmp.next = p.next28             p.next = tmp29             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

小白觉得四本书的例子,貌似可以更有助于解释代码,欢迎大侠拍砖指导。

leetcode 【 Reverse Linked List II 】 python 实现