每日一练：LeeCode-LCR 123. 图书整理 I （反转链表）（简）【栈、头插法（虚拟头结点）、双指针、递归】

本文是力扣LeeCode-LCR 123. 图书整理 I （简） 学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

示例 1：
输入：head = [3,6,4,1]
输出：[1,4,6,3]

提示：
0 <= 链表长度 <= 10000

很明显这道题的意思就是反转链表，笔者在这总结了4种方法，供大家参考。
这道题可以使用栈、头插法、双指针、递归等方法，推荐使用头插法

头插法（虚拟头结点）

使?虚拟头结点，通过头插法实现链表的反转（不需要栈）,建议画图模拟一下

class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head==null)return new int[]{};
        if(head.next==null)return new int[]{head.val};
        ListNode dummy = new ListNode(-1);	 创建虚头结点
        dummy.next = null;

        ListNode cur = head;
        int count = 0;
        // 遍历所有节点
        while(cur!=null){
            ListNode temp = cur.next;	//保存cur的下一节点，迭代使用
            // 头插法
            cur.next = dummy.next;	
            dummy.next = cur;
            cur = temp;
            count++;
        }
        //满足题意，主要流程为上面
        int[] res = new int[count];
        for(int i=0;i<count;i++){
            res[i] = dummy.next.val;
            dummy=dummy.next;
        }
        return res;
    }
}

时间复杂度: O(n)
空间复杂度: O(1)

栈方法

• ?先将所有的结点?栈
• 然后创建?个虚拟虚拟头结点，让cur指向虚拟头结点。然后开始循环出栈，每出来?个元素，就把它加?到以虚拟头结点为头结点的链表当中，最后返回即可

class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head==null)return new int[]{}; //如果链表为空，返回空数组
        if(head.next==null)return new int[]{head.val}; //如果链表中只有?个元素，则直接返回该元素数组
        Stack<ListNode> stack = new Stack<>();	 创建栈 每?个结点都?栈
        ListNode cur = head;
        while(cur!=null){
            stack.push(cur);
            cur = cur.next;
        }

		// 创建?个虚拟头结点
        ListNode dummy = new ListNode(0);
        cur = dummy;	//指针传递
        int size = stack.size();
        while(!stack.isEmpty()){
            ListNode node = stack.pop();
            cur.next = node;
            cur = cur.next;
        }
        cur.next = null;	//最后?个元素的next=null，否则成环了

		//满足题意，主要流程为上面
        int[] res = new int[size];
        for(int i=0;i<size;i++){
            res[i] = dummy.next.val;
            dummy=dummy.next;
        }
        return res;
    }
}

双指针法

class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head==null)return new int[]{};
        if(head.next==null)return new int[]{head.val};
        ListNode cur = head;
        ListNode pre = new ListNode(0);
        pre = null;
        int count = 0;
        while(cur!=null){
            ListNode temp = cur.next;	// 保存?下 cur的下?个节点，因为接下来要改变cur->next
            cur.next = pre;	// 翻转操作
			// 更新pre和cur,准备作下一次循环
            pre = cur;
            cur = temp;

            count++;
        }
        //满足题意，主要流程为上面
        int[] res = new int[count];
        for(int i=0;i<count;i++){
            res[i] = pre.val;
            pre=pre.next;
        }
        return res;
    }
}

时间复杂度: O(n)
空间复杂度: O(1)

递归

这种方法和双指针异曲同工，有了双指针的理解，这种方法，可以直接写出来

class Solution {
    private static int count = 0;
    public int[] reverseBookList(ListNode head) {
        if(head==null)return new int[]{};
        if(head.next==null)return new int[]{head.val};

        ListNode pre = reverse(null,head);
        int[] res = new int[count];
        for(int i=0;i<count;i++){
            res[i] = pre.val;
            pre=pre.next;
        }
        return res;
    }

    private ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null)return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        count++;
		// 递归的写法，其实就是做了双指针法这两步
		// pre = cur;
		// cur = temp;
        return reverse(cur,temp);
    }
}

这种方法，笔者还没通过提交，但是单独测试报错的例子，也可以通过，有点百思不得其解，望大佬指出问题。

时间复杂度: O(n), 要递归处理链表的每个节点
空间复杂度: O(n), 递归调?了 n 层栈空间

大家有更好的方法，请不吝赐教。