92. Reverse Linked List II

1. 原始题目

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

2. 题目理解

将m至n的链表反转。注意下标这里在链表中实际上是m-1至n-1。

我的思路是先遍历m步，然后在n-m+1遍历过程中将结点反转。然后将这一整段链表重新链接即可。这样做一个缺点就是需要多个标记点。

3. 解题

 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     def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
 9         if not head.next:
10             return head
11         m = m-1                  # 修正下标
12         n = n-1
13         dummy = ListNode(0)
14         dummy.next = head
15         record = dummy
16         
17         for _ in range(m):       # 先走到需要反转的地方
18             dummy = dummy.next
19             
20         end = dummy.next         # 记录断点
21         i = dummy
22         j = i.next               # i，j，k 负责反转链表
23         if j:
24             k = j.next
25             for _ in range(n-m+1):    
26                 if j:
27                     j.next = i
28                     i = j
29                     j = k
30                     if k:
31                         k = k.next
32         else:
33             return head
34         dummy.next = i          # 重新链接链表一端
35         end.next = j            # 重新连接链表另一端
36             
37         return record.next

验证：

 1 # 新建链表1
 2 listnode1 = ListNode_handle(None)
 3 s1 = [1,2,3,44,555,66,7,8]
 4 for i in s1:
 5     listnode1.add(i)
 6 
 7 listnode1.print_node(listnode1.head)
 8 
 9 s = Solution()
10 head = s.reverseBetween(listnode1.head,4,5)
11 listnode1.print_node(head)

1 2 3 44 555 66 7 8
1 2 3 555 44 66 7 8

LeetCode上有另一种解题思路和我的极其类似：这里粘过来对比学习一下：

 1 class Solution(object):
 2     def reverseBetween(self, head, m, n):
 3         """
 4         :type head: ListNode
 5         :type m: int
 6         :type n: int
 7         :rtype: ListNode
 8         """
 9         if not head or m == n: return head
10         p = dummy = ListNode(None)
11         dummy.next = head
12         for i in range(m-1): p = p.next
13         tail = p.next
14 
15         for i in range(n-m):
16             tmp = p.next                  # a)
17             p.next = tail.next            # b)
18             tail.next = tail.next.next    # c)
19             p.next.next = tmp             # d)
20         return dummy.next

流程如下：