链表内指定区域反转

发表于

描述

将一个节点数为 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≤1000 ， 0<m≤n≤size ，链表中每个节点的值满足 ∣val∣≤1000

示例1

1
2
输入: {1,2,3,4,5},2,4
返回: {1,4,3,2,5}

示例2

1
2
输入: {5},1,1
返回: {5}

题解

双指针、两次遍历

要反转局部链表,可以将该局部部分当作完整链表进行反转

再将已经反转好的链表与其他节点建立连接,重构链表

  1. 我们可以在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置开始反转，在多了一个表头的情况下就能保证第一个节点永远不会反转，不会到后面去
  2. 使用两个指针，一个指向当前节点，一个指向前序节点
  3. 依次遍历链表，到第m个的位置
  4. 对于从m到n这些个位置的节点，依次断掉指向后续的指针，反转指针方向
  5. 返回时去掉我们添加的表头
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
33
34
package main

type ListNode struct{
    Val int
    Next *ListNode
}


/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
*/
func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
    dummy := &ListNode{Next: head}
    pre := dummy

    for index := 1; index < m; index++ {
        pre = pre.Next
    }

    cur := pre.Next
    for index := m; index < n; index++ {
        temp := cur.Next
        cur.Next = temp.Next
        temp.Next = pre.Next
        pre.Next = temp
    }

    return dummy.Next
    
}