是熊是猫溜溜

子非鱼，焉知鱼之乐

leetcode 92 反转链表 II

发表于 更新于 分类于
本文字数： 6.3k 阅读时长 ≈ 6 分钟

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

原题介绍

示例一

digraph leetcode_92_1 { 
bgcolor="#f7f7f7"

rankdir=LR
subgraph cluster_name {
    
    subgraph cluster_1 {
        n0 [label="1" shape=circle,color=blue,fillcolor=white,style=filled]
        n1 [label="2" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        n2 [label="3" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        n3 [label="4" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        n4 [label="5" shape=circle,color=blue,fillcolor=white,style=filled]
        rank=same;
        n0 -> n1 -> n2 -> n3 -> n4 
        style=invis
    }

    subgraph cluster_2 {
        r0 [label="1" shape=circle,color=blue,fillcolor=white,style=filled]
        r1 [label="4" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        r2 [label="3" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        r3 [label="2" shape=circle,color=blue,fillcolor=lightblue,style=filled]
        r4 [label="5" shape=circle,color=blue,fillcolor=white,style=filled]

        rank=same;
        r0 -> r1 -> r2 -> r3 -> r4 
        style=invis
    }    

    n2 -> r2[constraint=false,color="red",pad=30]    

}

label=<<B>图 1.1 算法示意图</B>>

}

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]

解题思路

遍历拆分链表

如下图所示，通过遍历以 [left，right]作为分界，把链表分为三个字表。

digraph leetcode_92_1 { 
bgcolor="#f7f7f7"

rankdir=LR
subgraph cluster_name {
    subgraph cluster_1 {
        n0 [label="1" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n1 [label="..." shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n2 [label="left-1" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n3 [label="left" shape=circle,color=red,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n4 [label="..." shape=circle,color=blue,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n5 [label="right" shape=circle,color=red,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n6 [label="right+1" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n7 [label="..." shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n8 [label="n" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        rank=same;
        n0 -> n1 -> n2
        n2 -> n3[style=dashed,color=red]
        n3 -> n4 -> n5
        n5 -> n6[style=dashed,color=red]
        n6 -> n7 -> n8
        style=invis
    }

}
label=<<B>图 2.1 遍历拆分链表</B>>

}

分别处理三个子表

  • 记录左边链表的head与end，记录右边链表的head。
  • 遍历中间链表存入到栈当中，然后依次弹出栈中节点并链接为一个新的链表，根据栈后进先出的特性，新链表必定顺序是反过来的。
  • 然后再依次按照左中右顺序拼接合并三个链表，得到最终结果。
digraph leetcode_92_1 { 
bgcolor="#f7f7f7"

rankdir=LR
subgraph cluster_name {
    subgraph cluster_1 {
        n0 [label="1" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n1 [label="..." shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n2 [label="left-1" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n3 [label="right" shape=circle,color=red,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n4 [label="..." shape=circle,color=blue,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n5 [label="left" shape=circle,color=red,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n6 [label="right+1" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n7 [label="..." shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n8 [label="n" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        rank=same;
        n0 -> n1 -> n2
        n2 -> n3[style=dashed,color=red]
        n3 -> n4 -> n5
        n5 -> n6[style=dashed,color=red]
        n6 -> n7 -> n8
        style=invis
    }

}
label=<<B>图 2.2 最终结果</B>>

}

代码实现

栈实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //1. 如果链表为空或者是单节点链表直接返回即可
        if (head == null || head.next == null){
            return head;
        }

        //2. 初始化节点栈
        Stack<ListNode> stack = new Stack<ListNode>();

        //3. 初始化左链表的end节点
        ListNode leftLinkedListEnd = null;

        //4. 初始化右链表的start节点
        ListNode rightLinkedListStart = null;

        //5. 定义链表索引，并初始化为1
        int idx = 1;

        //6. 循环遍历链表
        for (ListNode it = head; it != null; it = it.next,idx++){
            //6.1 如果是处于[left,right]之间的节点，则存入栈中
            if ( idx >= left && idx <= right){
                stack.push(it);
            }
            //6.2 如果是处于[1,left)之间的节点，则记录其end节点
            else if (idx < left){
                leftLinkedListEnd = it;
            }
            //6.3 如果是处于(right,n]之间的节点，则记录其start节点，并跳出循环结束遍历
            else {
                rightLinkedListStart = it;
                break;
            }
        }

        //7. 依次弹出栈中元素反转中间链表
        ListNode midLinkedListHead = null;
        ListNode midLinkedListEnd = null;
        while (!stack.empty()){
            if (midLinkedListHead == null) {
                midLinkedListHead = stack.pop();
                midLinkedListEnd = midLinkedListHead;
                midLinkedListEnd.next = null;
            }else {
                midLinkedListEnd.next = stack.pop();
                midLinkedListEnd = midLinkedListEnd.next;
                midLinkedListEnd.next = null;
            }
        }

        //8. 合并左链表
        if (leftLinkedListEnd != null){
            leftLinkedListEnd.next = midLinkedListHead;
        }else {
            head = midLinkedListHead;
        }

        //9. 合并右链表
        if (rightLinkedListStart != null){
            midLinkedListEnd.next = rightLinkedListStart;
        }

        //10. 返回最终链表head节点
        return head;
    }
}

递归实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    //1. 临时节点
    private ListNode node;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //2. 判空处理
        if (head == null || head.next == null) {
            return head;
        }

        //3. 递归处理
        return reverse(head, left, right);
    }

    /**
     * reverse 前n个元素
     *
     * @param head 表头
     * @param n    前n个元素
     * @return 新表节点
     */
    private ListNode reverse(ListNode head, int n) {
        //1. n==1表示一个元素直接返回，并记录后区节点
        if (n == 1) {
            this.node = head.next;
            return head;
        }

        //2. 递归得到head.next后面的反转
        ListNode end = reverse(head.next, n - 1);

        //3. 反转 head 和 end
        head.next.next = head;

        //4. 新的尾节点指向保存的后驱节点
        head.next = this.node;
        return end;
    }

    /**
     * reverse 中间n个元素
     *
     * @param head  表头
     * @param left  左边界
     * @param right 有边界
     * @return 新表节点
     */
    private ListNode reverse(ListNode head, int left, int right) {
        //1. 如果left == 1 递归反转前n个元素
        if (left == 1) {
            return reverse(head, right);
        }

        //2. 递归找到待反转起始位置
        head.next = reverse(head.next, left - 1, right - 1);
        return head;
    }
}

附录

原题地址