反转链表
- 准备工作
- 1）ListNode基本结构
- 2）初始化ListNode集合
- 解法一：遍历创建新节点
- 解法二：两组List，面向对象操作
- 解法三：递归调用
- 解法四：直接移动
- 解法五：解法二的面向过程
Leetcode 206 反转链表
准备工作
1）ListNode基本结构
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
ListNode node = this;
StringBuilder sb = new StringBuilder();
while (node != null) {
sb.append(node.val).append("->");
node = node.next;
}
sb.append("NULL");
return sb.toString();
}
}
2）初始化ListNode集合
public class ListNodeInit {
public static ListNode getInitList() {
ListNode tailf = new ListNode(5, null);
ListNode node4 = new ListNode(4, tailf);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
return new ListNode(1, node2);
}
}
解法一：遍历创建新节点
新增一个ListNode newList集合，然后直接遍历目标ListNode initList集合，每遍历一个节点就创建一个新节点，并且将新节点添加到我们newList中
public class 反转链表1 {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----反转后-----");
System.out.println(reverseList(initList));
}
private static ListNode reverseList(ListNode initList) {
ListNode newList = null;
ListNode p = initList;
// 遍历到原链表的节点
while (p != null) {
int val = p.val;
// 创建一个新节点，新节点的下一个节点是之前的数据（将新值添加到头部）
newList = new ListNode(val, newList);
p = p.next;
}
return newList;
}
}
解法二：两组List，面向对象操作
构建一个包装类List集合，用于封装addFirst、removeFirst方法，思路为移除oldList头部节点，然后添加到新的newList的头部
public class 反转链表2 {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----反转后-----");
System.out.println(reverseList(initList));
}
private static ListNode reverseList(ListNode initList) {
List oldList = new List(initList);
List newList = new List(null);
while (true) {
// 原集合不停移除头部元素
ListNode removedNode = oldList.removeFirst();
if (removedNode == null) {
break;
}
// 新集合不停添加到头部（类比栈）
newList.addFirst(removedNode);
}
return newList.head;
}
static class List {
ListNode head;
public List(ListNode head) {
this.head = head;
}
/**
* 向头部添加节点
*/
public void addFirst(ListNode node) {
node.next = head;
head = node;
}
/**
* 向尾部添加节点
*/
public ListNode removeFirst() {
ListNode removedList = head;
if (head != null) {
head = head.next;
}
return removedList;
}
}
}
解法三：递归调用
利用递归后续遍历的回溯，能够反向拿到每一个元素的特点，不断的向initList尾部追加我们需要的逆序链表
public class 反转链表3 {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----反转后-----");
System.out.println(reverseList(initList));
}
private static ListNode reverseList(ListNode initList) {
if (initList == null || initList.next == null) {
return initList;
}
// initList.next.val最多为5，因为5.next.val为null。即initList.val最多为4
ListNode node = reverseList(initList.next);
// 第一次调用时：
// 5 -> 4,3,2,1 && 4 -> null
// 第二次调用时：
// 4 -> 3,2,1 && 3 -> null
// 第三次调用时：
// 3 -> 2,1 && 2 -> null
// 此处递归为后续遍历，可获取5,4,3,2,1顺序的值。
// 步骤1）拿到node节点后，将当前node和其head部分分开，将node的head部分的上一个节点赋值到node的next，
// 步骤2）且同时切断node和其head部分之间的关联
//
// 补充：前面提到initList.next.val最多为5，所以initList.next.next就是5的下一个节点
initList.next.next = initList;
initList.next = null;
return node;
}
}
解法四：直接移动
有点像选择排序，对两个元素进行互换位置，只不过此处为链表，难度大于数组。通过指针的关联关系，硬操作集合本身，每拿到一个节点，都将节点移动到头部
执行流程：
指针移动效果：
public class 反转链表4 {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----反转后-----");
System.out.println(reverseList(initList));
}
private static ListNode reverseList(ListNode o1) {
if (o1 == null || o1.next == null) {
return o1;
}
// 1、设置o1、o2、n1三者之间的关系
ListNode o2 = o1.next;
ListNode n1 = o1;
while (o2 != null) {
// 2、断开o2节点：o1的下一个节点本来是指向o2，现在直接修改为指向o2的下一个节点，所以能够断开
o1.next = o2.next;
// 3、o2添加到头部：o2的下一个节点是n1节点，n1表示新节点的头部
o2.next = n1;
// 4、修正n1的位置：在赋初值的时候，n1代表头部节点，由于上一步头部添加一个一个o2，所以n1不是头部，此处重新指向到头部
n1 = o2;
// 5、修正o2的位置：由于前面o2节点执行到了头部，此处将o2节点重新指向下一个需要处理的节点，即o1的下一个
o2 = o1.next;
}
return n1;
}
}
解法五：解法二的面向过程
与解法二思想相同，解法二为面向对象，此处为面向过程；
与解法四的区别为此处将原来的List集合一分为二，移动节点位置本身，没有太大的区别
public class 反转链表5 {
public static void main(String[] args) {
ListNode initList = ListNodeInit.getInitList();
System.out.println(initList);
System.out.println("-----反转后-----");
System.out.println(reverseList(initList));
}
private static ListNode reverseList(ListNode initList) {
if (initList == null || initList.next == null) {
return initList;
}
// 1、初始化o1、o2、n1三者之间的关系
ListNode n1 = null;
ListNode o1 = initList;
ListNode o2 = null;
while (o1 != null) {
// 2、标记处理节点的下一个节点：用于标记剩余待处理节点的头节点
o2 = o1.next;
// 3、构建新list：o1表示要处理的节点，n1为初始化节点，此处将初始化节点和在处理的o1节点进行关联
o1.next = n1;
// 4、修正新list的头节点：经过上面的赋值，n1位置已经向后移动一个，此处调整
n1 = o1;
// 5、修正待处理list的头节点：经过上面的赋值，此时o1指向新集合的头部，此时借助前面的o2，将o1的位置修正为待处理list的头部
o1 = o2;
}
return n1;
}
}
