leetcode 92 反转链表 II
z
 2019-07-04 21:51:02  

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or m == n:
            return head
        dump = TreeNode(-1)
        dump.next = head
        pre = dump
        for i in range(m-1):
            pre = pre.next
        
        p = pre.next
        for i in range(n-m):
            nex = p.next
            p.next = nex.next
            nex.next = pre.next
            pre.next = nex
        
        return dump.next

  • 逻辑上稍微有点绕

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    1->2->3->4->5->NULL, m = 2, n = 4

    先找到开始反转位置的前一个节点

      1->2->3->4->5->NULL
      *
     prev
     
     
      1->2->3->4->5->NULL
      *     *
     prev   nex
     
         +-----+
         |     V
      1->2  3->4->5->NULL
      *     *
     prev   nex
     
         +-----+
         |      V
      1->2  3  4->5->NULL
         ^  |
         +--+
         
      +-----+  
      |     |
      |  +--|----+
      |  |  v    v
      1  2  3  4->5->NULL
         ^  |
         +--+