算法练习：BM2 链表内指定区间反转

问题描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度O(1)。例如：给出的链表为 1→2→3→4→5→NULL, m=2,n=4,返回 1→4→3→2→5→NULL.

数据范围： 链表长度 0<size≤10000，0<m≤n≤size，链表中每个节点的值满足 val∣≤10000

要求：时间复杂度 O(n) ，空间复杂度 O(n)

进阶：时间复杂度O(n)，空间复杂度O(1)

示例1

输入：

{1,2,3,4,5},2,4

返回值：

{1,4,3,2,5}

示例2

输入：

{5},1,1

返回值：

{5}

解题思路

如果要空间复杂度小，就不能copy链表，只能做指针转换，用循环将指针颠倒，具体方法如图示：

设定指针变量

（为了方便图示，假设区间长度大于1，如果区间等于1，直接返回，不需要变换）

• 先找到子区间的第一个节点，定义为sub_head
• 它的前一个节点定义为 pre_fix
• 子区间的第一个节点变量为pre（与sub_head不同，这个变量会移动）
• 子区间第二个变量为curr，定义为当前pre的下一个节点，这个变量是这次翻转的当前变量
• 子区间第三个变量为next，定义为当前curr的下一个节点

进行翻转

• 将pre_fix 的下一个节点指向curr （区间外的最后一个节点指向子区间当前尾节点）
• 将sub_head 的下一个节点指向next （区间内的第一个节点指向区间外的第一个节点）
• 将curr 的下一个节点指向pre （节点翻转）

移动指针

• 将pre 赋值为当前的curr指向的节点
• 将curr 赋值为当前的next指向的节点
• next赋值为当前的curr指向的下一个节点（循环开始做）

循环

以上1-3步骤，根据区间长度，可以多次循环，最终得到结果。

代码

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def convertLisNode(mylist) -> ListNode:
  head_node = None
  prev_node = None
  for item in mylist:
    new_node = ListNode(item)

    if head_node == None:
      head_node = new_node
    else:
      prev_node.next = new_node

    prev_node = new_node

  return head_node

def reverse_list(head, m, n):
    if not head or m == n:
        return head

    dummy = ListNode(-1)
    dummy.next = head
    pre_fix_Node = dummy

    # Move pre pointer to the m-th node
    for _ in range(m - 1):
        pre_fix_Node = pre_fix_Node.next

    print("pre_fix_Node:" , pre_fix_Node.val)
    # Reverse the list between m-th and n-th nodes

    pre = pre_fix_Node.next
    sub_head = pre
    curr = pre.next
    for _ in range(n - m):
      next = curr.next
      #---------------------------
      pre_fix_Node.next = curr
      sub_head.next = next
      #---------------------------
      curr.next = pre
      pre = curr
      curr = next
  
    return dummy.next

initList = {5,7,8,9,12,13}
m = 2
n = 5
newNode = convertLisNode(initList)

# Print the new linked list
curr = newNode
while curr is not None:
  print(curr.val, end=" ")
  curr = curr.next

print("\n")
revNode = reverse_list(newNode,m,n)
# Print revNode linked list
curr = revNode
while curr is not None:
  print(curr.val, end=" ")
  curr = curr.next

小技巧

指针编程变量的指向非常搞，很容易出错，下面的网站可以可视化的看到变量的分配和实际运行效果，推荐尝试：

Online Python compiler, visual debugger, and AI tutor