206. 反转链表

206. 反转链表

递归解法：

时间复杂度：O(n)
空间复杂度：O(2^n)

class Solution {
    public ListNode reverseList(ListNode head) {
        // - 如何单链表 为空 或者只有一个节点 那么直接返回这个单链表
        if(null == head || null == head.next){
            return head;
        }

        // - 递归查询下一个节点 直到下一个节点为空的时候 才会 走下一行代码
        ListNode newHead = reverseList(head.next);

        // - head = 4 , head.next = 5 , head.next.next = null 
        // - 将 5 的下一个节点 指向 4 
        head.next.next = head;
        // - 将 4 指向 5 的指针 设置为空 
        head.next = null;

        / / - 返回处理后的结果
        return newHead;
    }
}

头插入法：

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    //- 使用头插入法
    public ListNode reverseList(ListNode head) {
        // - 初始化虚拟头节点
        ListNode dummy = new ListNode(0);
        // - 头节点移动的指针
        ListNode pre = dummy;
        // - 当前节点指针
        ListNode cur = head;
        //  - 如果当前单链表不为空则进行循环
        while (null != cur){
            // - 当前节点 赋值 给临时节点
            ListNode temp = cur;
            // - 当前节点的下一个节点 指向 当前节点
            cur = cur.next;
            // - 当前节点的临时节点的指针 指向 虚拟头节点的下一个节点
            temp.next = pre.next;
            // - 虚拟头节点的下一个节点 指向 临时节点
            pre.next = temp;
        }
        return dummy.next;
    }

}

恋上数据结构与算法老师解法：

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        // - 初始化头节点为空！
        ListNode newHead = null;
        while (null != head){
            // - 临时节点指向下一个节点
            ListNode temp = head.next;
            // - 下一个节点 指向 初始化的头节点
            head.next = newHead;
            // - 初始化头节点 指向 当前节点
            newHead = head;
            // - 当前节点 指向 临时节点
            head = temp;
        }
        return newHead;
    }

}