92. 反转链表 II(中等)twiceFor

Posted on In Views:

1，问题描述

92. 反转链表 II

难度：中等

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

示例 1：

img

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

示例 2：

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

提示：

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

进阶： 你可以使用一趟扫描完成反转吗？

2，初步思考

​ 第一次想到的解法是，截取子链表，然后进行翻转，最后进行重组！

​ 查看官方题解之后，想到了翻转链表中的迭代法翻转

3，代码处理

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
83
84
85
86
87
88
import support.ListNode;

public class _92反转链表II {

    // 方法二：一次遍历「穿针引线」反转链表（头插法）
    public ListNode reverseBetween_iteration(ListNode head, int m, int n) {
        if (m == n) return head;
        ListNode headNew = new ListNode();
        headNew.next = head;
        ListNode tail = headNew;
        int counter = 0;

        ListNode childHeadBefore = null;
        while (tail != null) {
            if (counter + 1 == m) {
                childHeadBefore = tail;
                tail = tail.next;
            } else if (counter + 1 > m && counter < n) {// 需要进行替换
                ListNode temp = tail.next;
                tail.next = tail.next.next;
                temp.next = childHeadBefore.next;
                childHeadBefore.next = temp;
            } else if (counter > n) {
                break;
            }else {
                tail = tail.next;
            }
            counter++;
        }
        return headNew.next;
    }
    // 0-1-2-【3】-4-【5】-6-7-8-9-10，childBefore=ok
    // 0-1-2-【5】-3-4-6-7-8-9-10

    // 解法1:截取、翻转、重组完成！！
    // 官方题解中的方法一：穿针引线，与此一致
    public ListNode reverseBetween_reverse(ListNode head, int m, int n) {
        if (m == n) return head;
        ListNode headNew = new ListNode();
        headNew.next = head;
        ListNode tail = headNew;

        ListNode childHeadBefore = null;
        ListNode childHead = null;
        ListNode childTail = null;
        ListNode childTailNext = null;
        int counter = 0;
        while (tail != null) {
            if (counter + 1 == m) {
                childHeadBefore = tail;
                childHead = tail.next;
            } else if (counter == n) {
                childTail = tail;
                childTailNext = tail.next;
                childTail.next = null;
                break;
            }
            tail = tail.next;
            counter++;
        }
        ListNode newHead = reverse(childHead);
        childHeadBefore.next = newHead;
        childHead.next = childTailNext;
        return headNew.next;
    }

    // 递归解决
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        _92反转链表II reverseList = new _92反转链表II();
//        ListNode listNode = reverseList.reverseBetween_iteration(ListNode.create((new int[]{1, 2, 3, 4, 5})), 2, 4);
//        ListNode listNode = reverseList.reverseBetween_iteration(ListNode.create((new int[]{5})), 1, 1);
        ListNode listNode = reverseList.reverseBetween_iteration(ListNode.create((new int[]{3,5})), 1, 2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}

参考链接：

https://leetcode.cn/problems/reverse-linked-list-ii/description/?envType=company&envId=bytedance&favoriteSlug=bytedance-thirty-days