【LeetCode刷题日记】：反转链表（面试基础考察）

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺反转链表题目背景LeetCode206给你单链表的头节点head请你反转链表并返回反转后的链表。示例 1输入head [1,2,3,4,5]输出[5,4,3,2,1]示例 2输入head [1,2]输出[2,1]示例 3输入head []输出[]提示链表中节点的数目范围是[0, 5000]-5000 Node.val 5000进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题双指针解法/ 双指针 class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; ListNode temp null; while (cur ! null) { temp cur.next;// 保存下一个节点 cur.next prev; prev cur; cur temp; } return prev; } }题目解析如果再定义一个新的链表实现链表元素的反转其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向直接将链表反转 而不用重新定义一个新的链表如图所示:我们只需要改变链表的next指针指向首先定义一个cur指针指向头结点再定义一个pre指针初始化为null。然后就要开始反转了首先要把 cur-next 节点用tmp指针保存一下也就是保存一下这个节点。不然会导致数据丢失为什么要保存一下这个节点呢因为接下来要改变 cur-next 的指向了将cur-next 指向pre 此时已经反转了第一个节点了。接下来就是循环走如下代码逻辑了继续移动pre和cur指针。最后cur 指针已经指向了null循环结束链表也反转完毕了。 此时我们return pre指针就可以了pre指针就指向了新的头结点。我们把cur的指向改变指向pre然后我们分别继续移动这两个指针cur的位置给pretemp的位置给cur都相当于是向后移动一次为什么先移动pre而不是先移动cur如果是先移动cur那么cur的值就被temp覆盖了pre的位置就改变不了了。递归解法// 递归 class Solution { public ListNode reverseList(ListNode head) { return reverse(null, head); } private ListNode reverse(ListNode prev, ListNode cur) { if (cur null) { return prev; } ListNode temp null; temp cur.next;// 先保存下一个节点 cur.next prev;// 反转 // 更新prev、cur位置 // prev cur; // cur temp; return reverse(cur, temp); } }解法解析递归的逻辑就是双指针的逻辑只是写起来的代码更简单些在这里我们定义了两个方法为什么需要两个方法因为我们要实现递归需要传递两个参数pre cur但是题目只给出了一个head因此reverseList(head)负责启动递归里面调用reverse(null, head)真正递归逻辑在reverse(prev, cur)里。具体流程假设原链表plaintext1 → 2 → 3 → 4 → 5 → null初始调用reverseList(head);进入reverse(null, 1);此时plaintextprev null cur 1第 1 层递归reverse (null, 1)temp cur.next 2cur.next prev →1 → null递归调用reverse(1, 2)链表现在plaintextnull ← 1 2 → 3 → 4 → 5 → null第 2 层递归reverse (1, 2)temp 3cur.next 1 →2 → 1调用reverse(2, 3)plaintextnull ← 1 ← 2 3 → 4 → 5 → null第 3 层递归reverse (2, 3)temp 43 → 2调用reverse(3,4)plaintextnull ← 1 ← 2 ← 3 4 →5 →null第 4 层递归reverse (3,4)temp 54→3调用reverse(4,5)第 5 层递归reverse (4,5)temp null5→4调用reverse(5, null)plaintextnull ←1 ←2 ←3 ←4 ←5最后一层cur null开始返回java运行if (cur null) return prev;这里 prev 是5然后一层层返回 5 → 最终回到 reverseList返回 5链表反转完成总结递归就是每次改变循环的位置替代循环reverse 就是保存下一个节点把当前节点指向前一个递归往后走走到 null 时prev 就是新头节点当前节点指向前一个然后递归下一组直到走到头最后那个节点就是新头。