第一部分：题目描述
⭐ 难度：简单
第二部分：题解
📑 ListNode类
public class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
2.1 方法一：生成新节点到新链表
构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的。
public static ListNode reverseList(ListNode head) { // 1.新链表的头节点，初始为 null ListNode newHead = null; // 2.指针 tmp 用于遍历 旧链表 ListNode tmp = head; // 3.进行链表遍历 while (tmp != null) { // 3.1 创建一个新节点 node，存储的val值为遍历到的旧链表的节点值 ListNode node = new ListNode(tmp.val); // 3.2 指定新节点的下一个节点为当前新链表头节点 node.next = newHead; // 3.3 将新节点 node 指定为新的新链表头节点 newHead = node; // 3.4 继续向后遍历旧链表 tmp = tmp.next; } // 4.返回新链表头节点 return newHead; }
优化：
public static ListNode reverseList(ListNode head) { // 1.新链表的头节点，初始为 null ListNode newHead = null; // 2.指针 tmp 用于遍历 旧链表 ListNode tmp = head; // 3.进行链表遍历 while (tmp != null) { // 3.1 创建一个新节点，并指定新节点的值为当前遍历到的旧链表节点值，下一个节点为当前新链表的头节点 // 修改新链表的头节点为创建的新节点 newHead = new ListNode(tmp.val, newHead); // 3.2 继续向后遍历旧链表 tmp = tmp.next; } // 4.返回新链表头节点 return newHead; }
评价：简单直白，就是得新创建节点对象。
2.2 方法二：复用旧节点到新链表
与方法1 类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点。
🍀 面向过程式思想方法
public static ListNode reverseList(ListNode head) { // 1.新链表的头节点，初始为 null ListNode newHead = null; // 2.指针 tmp 用于遍历 旧链表 ListNode tmp = head; // 3.进行链表遍历 while (tmp != null) { // 3.1 临时存储 tmp 的下一个节点 ListNode node = tmp.next; // 3.2 指定 tmp 的下一个节点为当前新链表的头节点，实际是为了拼接已存在的新链表节点 tmp.next = newHead; // 3.3 设置新链表的头节点为 当前tmp指针指向的节点 newHead = tmp; // 3.4 设置 tmp指针 指向临时存储的节点 tmp = node; } // 4.返回新链表头节点 return newHead; }
🍀 面向对象式思想方法
我们还可以使用另一种方式来表达该方法的意思：【更加面向对象，如果实际写代码而非刷题，更多会这么做】
static class List { ListNode head; public List(ListNode head) { this.head = head; } /** * 移除第一个节点 * * @return 被移除的节点 */ public ListNode removeFirst() { // 1.获取原链表的第一个节点 ListNode first = head; // 2.如果存在节点，则将被删除的节点的下一个节点设置为新的头节点 if (first != null) { head = first.next; } // 3.返回被删除的节点 return first; } /** * 添加节点到第一个元素的位置（作为头节点） * * @param first 需要添加作为新头节点的节点 */ public void addFirst(ListNode first) { // 1.设置新头节点的下一个节点为原头节点，目的是进行链表节点拼接 first.next = head; // 2.设置新节点为新头节点 head = first; } } public static ListNode reverseList(ListNode head) { // 1.设置 旧链表 List oldList = new List(head); // 2.设置 新链表 List newList = new List(null); // tmp指针用于遍历 ListNode tmp = null; // 3.移除旧链表的当前头节点 node，赋给 tmp。 // 如果不为空说明移除成功，如果为空说明已经全部遍历完旧链表，旧链表已无节点 while ((tmp = oldList.removeFirst()) != null) { // 4.将从旧链表移除的头节点 node 添加到新链表的头部作为新的头节点 newList.addFirst(tmp); } // 5.返回新链表的头节点 return newList.head; }
2.3 方法三：递归
下面为伪码调用过程，假设节点分别是 1→2→3→4→5→null，先忽略返回值。
reverseList(ListNode p = 1) { reverseList(ListNode p = 2) { reverseList(ListNode p = 3) { reverseList(ListNode p = 4) { reverseList(ListNode p = 5) { if (p == null || p.next == null) { return p; // 返回5 } } // 此时p是4, p.next是5 } // 此时p是3, p.next是4 } // 此时p是2, p.next是3 } // 此时p是1, p.next是2 }
接下来，从 p = 4 开始，要让 5→4，4 → 3
reverseList(ListNode p = 1) { reverseList(ListNode p = 2) { reverseList(ListNode p = 3) { reverseList(ListNode p = 4) { reverseList(ListNode p = 5) { if (p == null || p.next == null) { return p; // 返回5 } } // 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.next=p // 还要注意4要指向 null, 否则就死链了 } // 此时p是3, p.next是4 } // 此时p是2, p.next是3 } // 此时p是1, p.next是2 }
最终代码为：
public static ListNode reverseList(ListNode head) { /* 以 旧链表为 1 -> 2 -> 3 为例 */ /* 递归终止条件是 curr.next == null，目的是到最后一个节点就结束递归 需要考虑空链表即 p == null 的情况 */ if (head == null || head.next == null) { return head; // 最后一个节点 } // 比如此时的 head.val 为 2 // 拿到最后一个节点为3 ListNode last = reverseList(head.next); // 节点3 的下一个节点指向 节点2 head.next.next = head; /* 节点2 的下一个节点不再指向 节点3 为什么要加这句话？ 主要是当递归回到 head.val 为1 的时候，如果不加这句话，则会导致 节点1 和 节点2 存在相互指向的问题， 而导致了在遍历新链表的时候会在 节点1 和 节点2 之间不断循环 */ head.next = null; // 每次递归方法返回的都是同样的值 —— 最后一个节点 return last; }
Q：为啥不能在递的过程中倒序？
A：比如
- $ 1 \rightarrow 2 \rightarrow 3 $ 如果递的过程中让 2→1 那么此时 2 → 3 就被覆盖，不知道接下来递给谁
- 而归的时候让 3 → 2 不会影响上一层的 1 → 2
评价：单向链表没有 prev 指针，但利用递归的特性 记住了 链表每次调用时相邻两个节点是谁
2.4 方法四：旧链表中移动旧节点
从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束。
public static ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } // 1.设置新链表 newHead 初始指向 旧链表的头节点 ListNode newHead = head; // 2.设置旧链表的头节点，由于 oldHead 不会更改，其实可以直接使用 head，但为了方便理解，还是单独使用一个指针 oldHead0 ListNode oldHead = head; // 用于指向当前需要移动的节点 ListNode tmp; // 3.节点移动 // 3.1 获取旧链表头节点的下一个节点，直到旧链表只剩下了一个节点即只有旧头节点 while ((tmp = oldHead.next) != null) { // 3.2 将 tmp 从旧链表中移除 oldHead.next = tmp.next; // 3.3 将 tmp 移动到新链表头节点的前面 tmp.next = newHead; // 3.4 将 tmp 设置为新链表新的头节点 newHead = tmp; } // 4.返回新链表新的头节点 return newHead; }
