算法 1.5.2 反转链表【leetcode 206】

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：
0 <= 节点个数 <= 5000

数据结构

• 链表

算法思维

• 遍历

解题要点

• 链表的特性

---

解题思路

一. Comprehend 理解题意

• 需要将链表逆序输出，结果作为新链表返回

二. Choose 选择数据结构与算法

解法一：遍历

• 数据结构：链表
• 算法思维：遍历

三. Code 编码实现基本解法

class Solution {
    
    public ListNode reverseList(ListNode head) {

        //0.非空判断
        if (head == null) return null;

        //1.遍历链表，将元素存入新链表中
        ListNode cur = head;
        ListNode newList = null;
        while (cur != null) {
            ListNode newNode = new ListNode(cur.val);
            newNode.next = newList;
            newList = newNode;
            cur = cur.next;
        }

        //2.返回新链表
        return newList;
    }

}

执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：38 MB，击败了 87.60% 的Java用户
时间复杂度：O(n) -- 链表的遍历 O(n)
空间复杂度：O(n) -- 新链表的内存空间 O(n)

四. Consider 思考更优解

优化代码结构
改变算法思维
借鉴其他算法

五. Code 编码实现最优解

=== 暂无 ===

六. Change 变形与延伸

• 进阶：能否用迭代或递归两种方法解决这道题？

迭代法：

class Solution {
    public static ListNode reverseListIterative(ListNode head) {
        ListNode prev = null; //前指针节点
        ListNode curr = head; //当前指针节点
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移
            curr.next = prev; //将当前节点指向它前面的节点
            prev = curr; //前指针后移
            curr = nextTemp; //当前指针后移
        }
        return prev;
    }
}

递归法：

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }

    private static ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null) return pre;
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(cur,next);
    }
}