力扣面试150题--反转链表 II

Day 34

题目描述

思路如下

首先解释一下如何原地反转链表，就题目所示
1-》2-》3-》4-》5
将2，3，4进行反转
1-》2-》《-3《-4 5
然后将1指向4 2指向5
1-》4-》3-》2-》5，就完成了反转
具体思路可以看代码

/**
 * 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(left==right){//左右都是同一元素不用处理
            return head;
        }
        ListNode fakehead=new ListNode();
        fakehead.next=head;//增加一个空的头结点，目的在于防止头结点找不到其前面的节点
        int i=0;
        ListNode tes=fakehead;
        while(i<left-1){
            tes=tes.next;
            i++;
        }//找到左边反转区间的前一个元素
        ListNode beg=tes;
        tes=tes.next;//指向反转区间的第一个元素
        i++;
        if(i+1==right){//如果反转区间只有两个元素
            ListNode end=tes.next.next;
            tes.next.next=tes;
            beg.next=tes.next;
            tes.next=end;
        }
        else{//说明区间内大于两个元素
            ListNode before=tes;
            tes=tes.next;//指向反转区间的第二个元素
            i++;
            while(i!=right){
                ListNode xia=tes.next;//将该节点的下一个序号记录下
                tes.next=before;//将该节点的下一个序号指向前一个元素
                before=tes;//将前一个元素更新为该元素
                tes=xia;//移动到下一个元素
                i++;
            }
            //此时tes指向反转区间的最后一个元素
            ListNode end=tes.next;//反转区间外右边的第一个元素
            tes.next=before;
            ListNode sm=beg.next;//取出反转区间左边的第一个元素
            sm.next=end;
            beg.next=tes;
        }
        return fakehead.next;



    }
}