反转链表，剑指offer，力扣

目录

解题方法：

难度分析：

解题思路（迭代）：

代码实现：

代码（递归）：

---

题目地址：

206. 反转链表 - 力扣（LeetCode）

难度：简单

今天刷反转链表，大家有兴趣可以点上看看题目要求，试着做一下。

我们直接看题解吧：

解题方法：

方法1、迭代（时间复杂度（1））

方法2、递归（时间复杂度（n））

难度分析：

这道题是不难，应该算是基础的题目了，递归方法比较难理解一点

解题思路（迭代）：

假设链表为1->2->3->null,我们需要把它改成null->1->2->3

在遍历链表时，将当前节点的next 指针改为指向前一个节点，由于节点没有设引用前一个节点，因此必须事先存储其前一个节点，在更改的引用之前，由于节点没有设引用前一个节点，最后返回新的头引用。

代码实现：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;//头节点
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = tmp;               // cur 访问下一节点
        }
        return pre;
    }
}
 
 
 

代码（递归）：

class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}