力扣92.反转指定范围内的链表、25.k个一组反转链表

92.反转指定范围内的链表

/**
 * 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) {
        //left是第left个节点
        ListNode dummy=new ListNode(0,head);
        int count=0;
        ListNode pre=dummy,cur=dummy,tailAfter;
        while (right-->0){
            cur=cur.next;
            count++;
            if  (count==left-1){
                pre=cur;
            }
        }
        tailAfter=cur.next;
        cur.next=null;
        ListNode newHead=reverseList(pre.next);
        pre.next.next=tailAfter;
        pre.next=newHead;
        return dummy.next;
    }
    public ListNode reverseList(ListNode root){
        if (root==null || root.next==null) return root;
        ListNode newHead=reverseList(root.next);
        root.next.next=root;
        root.next=null;
        return newHead;
    }
}

25.k个一组反转链表

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy=new ListNode(0,head);
        ListNode cur=dummy,pre=dummy,tail,tailAfter;
        int copyk;
        while (true){
            copyk=k;
            while (cur!=null && copyk-->0){
                cur=cur.next;
            }
            if (copyk>0 || cur==null) break;
            //为反转做准备
            tailAfter=cur.next;
            cur.next=null;
            ListNode newhead=reverseList(pre.next);
            pre.next.next=tailAfter;
            tail=pre.next;
            pre.next=newhead;

            //为下一次做准备
            pre=tail;
            cur=tail;
        }
        return dummy.next;
    }
    public ListNode reverseList(ListNode root){
        if (root==null || root.next==null) return root;
        ListNode newhead=reverseList(root.next);
        root.next.next=root;
        root.next=null;
        return newhead;
    }
}