链表linkedlist系列

92. Reverse Linked List II Medium

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5] 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

/**
 * 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 l, int r) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode leftpre = pre,rightpre=pre;
        //leftpre指向left的前一个
        for(int i=1;i<l;i++)  leftpre=leftpre.next;
        //rightpre指向right当前，记住这里是当前，不是前一个！
        for(int i=1;i<=r;i++) rightpre=rightpre.next;
        //left指向要反转的第一个node
        ListNode left=leftpre.next;
        //right指向第一个不反转的node
        ListNode right = rightpre.next;
        //防止死循环
        rightpre.next=null;
        //反转前的第一个为反转后的最后一个
        ListNode lefttail = left;
        //进行反转，并将反转结果对接leftpre
        leftpre.next = reverse(left);
        //对接反转自后一个与未反转部分
        lefttail.next=right;
        return pre.next;
    }
    //简单的链表反转过程
    public ListNode reverse(ListNode head){
        ListNode pre = new ListNode(0);
        while(head!=null){
            ListNode temp=pre.next;
            pre.next=head;
            head=head.next;
            pre.next.next=temp;
        }
        return pre.next;
    }
}

25. Reverse Nodes in k-Group Hard

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Example 3:

Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]

Example 4:

Input: head = [1], k = 1
Output: [1] 

Constraints:

• The number of nodes in the list is in the range sz.
• 1 <= sz <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= sz


/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode node = head;
        //1.找到第k+1个点的位置
        for(int i=0;i) {
            if(node==null) return head;//如果不够k个点不需要反转
            node = node.next;
        }
        //对前k个点进行反转，反转后产生newHead,之前的head指向k个元素的末尾，下一步递归调用要用到
        ListNode newHead = reverse(head,k);
        //递归调用进行下一组k个元素的反转
        head.next = reverseKGroup(node,k);
        return newHead;
    }
    //用于反转一个数组的前k个元素
    private ListNode reverse(ListNode head, int k){
        ListNode pre = null,curr=head;
        for(int i=0;i){
            ListNode next = curr.next;
            curr.next = pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
}

 2074. Reverse Nodes in Even Length Groups

Medium

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

• The 1st node is assigned to the first group.
• The 2nd and the 3rd nodes are assigned to the second group.
• The 4th, 5th, and 6th nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Example 1:

Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurrs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurrs.
- The length of the last group is 4, which is even, hence the nodes are reversed.

Example 2:

Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurrs.

Example 3:

Input: head = [1,1,0,6,5]
Output: [1,0,1,5,6]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 2. The nodes are reversed.

Example 4:

Input: head = [2,1]
Output: [2,1]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the last group is 1. No reversal occurrs.

Example 5:

Input: head = [8]
Output: [8]
Explanation: There is only one group whose length is 1. No reversal occurrs. 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 105

/**
 * 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 reverseEvenLengthGroups(ListNode head) {
        if(head==null) return null;        
        return reverseK(head,1,countList(head));
    }
    private int countList(ListNode head){
        int count = 0;
        while(head!=null) {
            head=head.next;
            count++;
        }
        return count;
    }
    private ListNode reverseK(ListNode head,int k,int remain){
        if(head==null) return null;
        ListNode node = head;
        if((remain>=k && k%2==0) || (remain//坑点：剩余不够k的情况下，要以剩余的节点数量来判定是否要反转
            for(int i=0;inull;i++) //要反转的情况下，直接将node指向下一轮反转的第一个点
                node=node.next;
            ListNode newHead = reverse(head,Math.min(k,remain));
            head.next = reverseK(node,k+1,remain-k);
            return newHead;
        }
        else{
            for(int i=0;inull&&node.next!=null;i++) //不反转的情况下，直接将node指向本轮反转的最后一个点，因为要与下一轮反转衔接
                node=node.next;
            node.next = reverseK(node.next,k+1,remain-k);
            return head;
        }
    }
    private ListNode reverse(ListNode head,int k){
        ListNode pre = null,curr=head;
        for(int i=0;i){
            if(curr==null) return pre;
            ListNode next = curr.next;
            curr.next = pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
}