92. 反转链表 II

题目#

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

说明: 1 ≤ mn ≤ 链表长度。

示例:

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

思路#

头插

代码#

func reverseBetween(head *ListNode, m int, n int) *ListNode {
if m == n {
return head
}
dummy := ListNode{
Val: 0,
Next: head,
}
var pre, cur *ListNode
cur = &dummy
i := 0
// 先走到 m-1 的位置
for ; i < m; i++ {
if i == m-1 {
pre = cur
}
cur = cur.Next
}
// 在 m-n 区间内做处理
for ; i >= m-1 && i <= n-1; i++ {
// 存一下
tmp := cur.Next
// 断链
cur.Next = cur.Next.Next
// 头插(放在 m-1 之后)
tmp.Next = pre.Next
pre.Next = tmp
}
return dummy.Next
}
Last updated on