链表反转-指定区间反转

LeetCode92: 给你单链表的头指 head 和两个整数 eft 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。
示例 1:
输入: head = [1,2,3,4,5], left = 2，right = 4
输出: [1,4,3,2,5]

思路：
头插法。
具体的，首先找到要反转的起始位置如，下图的2就是起始位置，然后在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

这个过程就是前面的带虚拟结点的插入操作，每走一步都要考虑各种指针怎么指，既要将结点摘下来接到对应的位置上，还要保证后续结点能够找到。代码如下：

public class ReverseListBetween {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        ListNode nodeA = initLinkedList(a);

        ListNode d = null;
        //头插法
        d = reverseBetween2(nodeA, 2, 4);
        System.out.println(toString(d));
    }

    
    /**
     * 头插法
     */
    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        // 设置 虚拟节点 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }


    /**
     * 初始化链表
     */
    private static ListNode initLinkedList(int[] array) {
        ListNode head = null, cur = null;

        for (int i = 0; i < array.length; i++) {
            ListNode newNode = new ListNode(array[i]);
            newNode.next = null;
            if (i == 0) {
                head = newNode;
                cur = head;
            } else {
                cur.next = newNode;
                cur = newNode;
            }
        }
        return head;
    }


    /**
     * 输出链表
     */
    public static String toString(ListNode head) {
        ListNode current = head;
        //StringBuilder可以用来拼接字符串
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(current.val).append("\t");
            current = current.next;
        }
        return sb.toString();
    }

    //定义链表节点
    static class ListNode {
        public int val;
        public ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82