当你穿过了暴风雨，你已不是原来那个人
—— 24.9.21
206. 反转链表
给你单链表的头节点
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
方法1
构造一个新链表，从旧链表依次拿到每个结点，创建新节点添加至新链表头部，完成后新链表即是倒序的
/*** Definition for singly-linked list.* 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; }* }*/ public ListNode reverseList(ListNode head) {ListNode prev = null;while (head != null) {prev = new ListNode(head.val, prev);head = head.next;}return prev;}
方法2
与方法1类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点
/*** Definition for singly-linked list.* 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; }* }*/
class Solution {public ListNode reverseList(ListNode head) {List list1 = new List(head);List list2 = new List(null);while (head != null) {ListNode remove = list1.removeFirst();if (remove == null){break;}list2.addFirst(remove);}return list2.head;}static class List {ListNode head;public List(ListNode head) {this.head = head;}public void addFirst(ListNode First){First.next = head;head = First;}public ListNode removeFirst(){if (head == null){return null;}ListNode thanRemove = head;head = head.next;return thanRemove;}}
}
方法3
用递归的方法，直接将链表进行翻转
注意：if的判断要左边先进行head是否为空的判断，在进行head.next是否为空的判断，否则力扣判题系统会进行报错，提示程序试图在 null 对象上调用方法或访问字段
/*** Definition for singly-linked list.* 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; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null){// 找到了最后一个节点return head;}ListNode last = reverseList(head.next);head.next.next = head;head.next = null;return last;}
}
方法4
从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束
1.设置指针 old1(旧头)、new1(新头)、old2(旧老二)，分别指向第一，第一，第二节点
new1old1(1)—>old2(2)—>3—>4—>5—>null
2.将 old2 节点从链表断开，即 old1 节点指向第三节点
new1old1(1)—>3—>4—>5—>null;old2(2)
3.old2 节点链入链表头部，即
old2(2)—>new1old1(1)->3—>4—>5—>null
4.new1 指向 old2
new1old2(2) —>old1(1) —>3—>4—>5—>null
5.old2 指向 old1 的下一个节点，即
new1(2)—>old1(1)—>old2(3)—>4—>5—>null
6.重复以上 2 ~ 5 步，直到 old2 指向 null
7.还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑
// 方法4 原始链表设置新旧两个指针进行复制public ListNode reverseList4(ListNode old1) {if (old1 == null || old1.next == null){return old1;}// 每次把原始链表的第二个结点剪切放到新链表的头部，当旧链表的第二个结点为null时，结束ListNode old2 = old1.next;ListNode new1 = old1;while (old2 != null) {old1.next = old2.next;old2.next = new1;new1 = old2;old2 = old1.next;}return new1;}
方法5
要点:把链表分成两部分，思路就是不断从链表2的头，往链表1的头搬移
1.new1 指向 null，代表新链表一开始没有元素，old1 指向原链表的首节点
new1(null),o1(1)—>2—>3—>4—>5—>null
2.开始循环，old2指向原链表次结点
new1(null),old1(1)—>old2(2)—>3—>4—>5—>null
3.挪移
old1(1)—>new1(null),old2(2)—>3—>4—>5—>null
4.指针复位
new(1)—>null,new1 old2(2)—>3—>4—>5—>null
5.重复2~4步
6.当old1 = null时，退出循环
// 方法5 面向过程同一链表互换public ListNode reverseList5(ListNode old1) {if (old1 == null || old1.next == null){return old1;}ListNode new1 = null;while (old1 != null) {ListNode old2 = old1.next;old1.next = new1;new1 = old1;old1 = old2;}return new1;}
