LeetCode-92.反转部分链表

发表于 分类于

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例：

1
2
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
1
2
输入：head = [5], left = 1, right = 1
输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

题解

整体思路：

  1. 给链表添加一个空表头，防止链表从head开始反转，head变化后返回值不确定性。增加空表头后，返回空表头的next指向的节点即可；

  2. 初始化两个指针，pre和cur，分别表示待反转区域的第一个节点 left 的前一个节点和待反转区间的第一个节点

  3. 遍历查找待反转区间的第一个节点，确定pre和cur

  4. 反转left和right之间的节点：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

    其中：

    cur：指向待反转区域的第一个节点 left，每次遍历都会变化；
    pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

链表结构：

1
2
3
4
5
6
7
8
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
  let res = ListNode(-1)
  res.next = head
  
  var pre: ListNode? = res
  var cur: ListNode? = head
  
  var i = 1
  while i < left {
    pre = cur
    cur = cur?.next
    i += 1
  }
  for _ in left ..< right {
    let temp = cur?.next
    cur?.next = temp?.next
    temp?.next = pre?.next
    pre?.next = temp
  }
  return res.next
}

复杂度分析：

时间复杂度：O(N)，其中N是链表总节点数。最多只遍历了链表一次，就完成了反转。

空间复杂度：O(1)。只使用到常数个变量。