【算法训练-链表 一】【反转链表】反转链表、区间反转链表、K个一组反转链表

输入：
{1,2,3}
返回值：
{3,2,1}

输入：
{}
复制
{}
说明：空链表则输出空

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 1 如果为空列表，返回null
        if (head == null) {
            return null;
        }
        // 2 定义双指针
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            // 存储下一个节点
            ListNode  pNext = cur.next;
            // 当前节点指向上一个[局部反转]
            cur.next = pre;
            // 双指针向后移动
            pre = cur;
            cur= pNext;
        }
        return pre;
    }
}

输入：
{1,2,3,4,5},2,4
返回值：
{1,4,3,2,5}

输入：
{5},1,1
返回值：
{5}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        // 1 设置虚拟头节点[避免当head节点位置改变且无明确位置的指针节点不知道该如何返回的情况]
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 2 双指针向后移动m步
        ListNode pre = dummy;
        ListNode cur = head;
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        // 3 m到n的区间链表要进行反转[下一个节点和已反转的子区间整体进行反转]
        for (int i = m; i < n; i++) {
            // 1 pNext 指向cur下一个节点，反转过程就是将这个节点插入到pre的下一个位置
            ListNode pNext = cur.next;
            // 2 cur指向下一个待转节点
            cur.next = pNext.next;
            // 3 pNext节点指向反转子区间的尾节点，成为反转子区间新的尾节点
            pNext.next = pre.next;
            // 4 pre指向反转子区间新的尾节点pNext
            pre.next = pNext;
        }
        return dummy.next;
    }
}

输入：
{1,2,3,4,5},2
返回值：
{2,1,4,3,5}

输入：
{},1
返回值：
{}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // 1 定义分组尾节点
        ListNode tail = head;
        // 2 划分本级处理的区间反转子任务
        for (int i = 0; i < k; i++) {
            if (tail == null) {
                // 2-1 任务停止条件是区间不足K个节点，此时直接返回这些节点即可
                return head;
            }
            tail = tail.next;
        }
         // 3 处理本级区间反转任务
        ListNode newHead = reverse(head, tail);
        //  4 剩余区间继续递归反转，直到全部反转
        head.next = reverseKGroup(tail, k);
        return newHead;
    }
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode pNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = pNext;
        }
        return pre;
    }
}

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度