题目描述

相同题目，在专题反转链表中有记录。🔗

迭代法

解题思路：
如下图所示，题目要求将链表反转。本文介绍迭代（双指针）、递归两种实现方法。
考虑遍历链表，并在访问各节点时修改 next 引用指向，算法流程见注释。
复杂度分析：
时间复杂度 O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间。

   /**
         * 简化方法（暂存后继节点）
         *
         * @param head
         * @return
         */
public ListNode reverseList(ListNode head) {
    ListNode cur = head, pre = null;
    while (cur != null) {
        ListNode temp = cur.next;   // 暂时保存后面一个节点
        cur.next = pre; // 交换指向
        pre = cur;
        cur = temp;
    }
    return head;
}

递归法

/**
         * 递归法
         *
         * @param head
         * @return
         */
public ListNode reverseList(ListNode head) {
    return recur(null, head.next);
}
public ListNode recur(ListNode pre, ListNode cur) {
    if (cur == null) return pre;    // 递归的中止条件
    ListNode temp = cur.next; // 保存下一个节点
    cur.next = pre;  // 转换指针指向
    return recur(cur, temp);    // 递归转换
}