LeetCode - 92 - 反转链表|| - java - 两种解法 - 细喔~_leetcode 92

题目

可以参考 这题LeetCode - 25. K 个一组翻转链表,因为我们第一种解放就与这题相同。

---

 

解法一

找到 链表 left ~ right 这个范围，将它“截取出来”，单独进行反转，反转完后，将之接回链表中，为了能够将其接回链表中，我们需要获取 left 的前驱节点，和 right 的后驱节点。（LeetCode - 25. K 个一组翻转链表）

---

 

跟着我一步步来

第一步： new 一个傀儡头节点 newHead，且 newHead.next == head。（这样做，我们就获得了 head 的 前驱节点。防止头节点head也是反转对象。）

---

 

第二步：在创建一个 节点引用 prev，用来记录 left的前驱节点（通过for循环，让prev指向 left的前驱节点）

---

 

第三步：寻找 right 位置的节点

---

 

第四步：记录 rightNode 的 下一个节点的位置（rightNode.next）,并将 prev.next（left位置的节点），rightNode 进行传参 给 反转方法myRreverse。

---

 

第五步： 敲写 myReverse 方法，（跟这题 LeetCode - 25. K 个一组翻转链表 一模一样）

---

 

第六步： 将 left 和 right 置回 初始位子（left <= right ）,并接回链表。最终返回逆序完成之后的原链表。

---

&ensp；

附上程序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || right == left){
            return head;// 头节点为null，链表为空，反转链表没有意义（没有节点给你反转）
            // right == left ，反转一个节点，等于没反转。也没有反转的意义
            // 直接返回 head
        }
        ListNode newHead = new ListNode(0,head);

        ListNode prev = newHead;
        for(int i = 0; i < left - 1; i++){
            prev = prev.next;
            if(prev == null){// 防止空指针异常，另外防止 left 位置不合法（链表节点没有那么多）
                return head;
            }
        }

        ListNode rightNode = prev.next;
        for(int i = 0;i < right - left;i++){
            rightNode = rightNode.next;
            if(rightNode == null){//防止空指针异常，另外防止 right 位置不合法（链表节点没有那么多）
                return head;
            }
        }
        
        ListNode rightNodeNext = rightNode.next;
        ListNode[] reverse = myReverse(prev.next,rightNode);
        prev.next = reverse[0];
        rightNode = reverse[1];

        rightNode.next = rightNodeNext;
        return newHead.next;
    }
    public static ListNode[] myReverse(ListNode left,ListNode right){
        ListNode prev = right.next;
        ListNode p = left;
        while( prev != right){
            ListNode pNext = p.next;
            p.next = prev;
            prev = p;
            p = pNext;
        }
        return new ListNode[]{right,left};

    }
}
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

---

 

解法二：

前面 跟解法一差不多（求 left位置的节点）。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || right == left){
            return head;// 头节点为null，链表为空，反转链表没有意义（没有节点给你反转）
            // right == left ，反转一个节点，等于没反转。也没有反转的意义
            // 直接返回 head
        }
        ListNode newHead = new ListNode(0,head);

        ListNode prev = newHead;
        for(int i = 0; i < left - 1; i++){
            prev = prev.next;
            if(prev == null){// 防止空指针异常，另外防止 left 位置不合法（链表节点没有那么多）
                return head;
            }
        }

        ListNode cur = prev.next;
        ListNode next = null;
        for(int i = 0;i < right -left;i++){
            next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        return newHead.next;

    }
}
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