LeetCode - 反转链表Ⅱ

前言：

😆对于链表的题目，首先要把握住它的结构特点。单链表，双向链表，不同的结构处理的方法则不同，但是不管怎样处理都需保证它原有的结构。

LeetCode链接

92. 反转链表 II - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list-ii/submissions/

题目：

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

示例1：

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

输出：[1,4,3,2,5] 

示例2：

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

输出：[5]

题目分析

🎈需要反转局部链表，首先记录局部前一个和后一个节点。由于已经存储了其他两部分的尾节点和首节点，那么就可以切断局部链表和后续的链接，反转完成后，再连接上即可。

🎈这样的想法只是针对于，反转区域在局部。如果是前半段，后半段，或者整个链表呢？显然这样的想法不成立。

🎈我们可以设置一个哨兵位节点，那么局部链表不管怎样分配，都可以保证前面有节点。如果局部链表分配到后半段，之前的思路也是ok的。因为可以认为尾节点的后一个节点就是null。所以这样处理，不管需要反转链表的局部在哪里，都可以确定它的前后都有节点。

代码实现

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head.next == null) {
            return head;
        }
 
        //哨兵位节点
        ListNode ret = new ListNode(-1);
        ret.next = head;
 
        //记录区域
        ListNode tmp1 = ret;
        ListNode tmp2 = ret;
        for(int i = 0; i < left - 1; i++) {
            tmp1 = tmp1.next;
        }
        for(int i = 0; i < right; i++) {
            tmp2 = tmp2.next;
        }
        ListNode tmp3 = tmp2;
        tmp2 = tmp2.next;
        tmp3.next = null;
 
        ListNode end = tmp1.next;
        ListNode begin = tmp3;
        //反转链表
        ListNode l1 = null;
        ListNode l2 = tmp1.next;
        ListNode l3 = tmp1.next.next;
        while(l2 != null) {
            l2.next = l1;
            l1 = l2;
            l2 = l3;
            if(l3 != null) {
                l3 = l3.next;
            }
        }
        //连接
        tmp1.next = begin;
        end.next = tmp2;
        return ret.next;
 
    }
}

小结：

🐵理清思路，把握技巧，锻炼思维方式。

🐵最后与大家共勉一句话：跋山涉水不改一往无前，山高路远但见风光无限。