算法日记-链表翻转
重温力扣常规算法，记录算法的演变，今天介绍的是链表翻转
场景：
现在有一条单项链表，链表节点存在一个数据和指向下一个节点的指针， 如何将其翻转过来？
输入 100->200->300->400->500
输出 500->400->300->300->100
针对该场景，我们有多种解决方式，这里我们介绍最常见的两种
解法一：迭代
从前往后遍历链表，处理当前节点时，需要将用额外的变量保存当前节点指向前后的节点指针，从而可以方便改变指针指向的具体信息，然后不停地重复该过程。下面我们来具体操作
步骤
1、定义链表节点结构ListNode，包含两个变量val和next
2、我们需要定义两个变量，变量的类型为ListNode，分别存储当前节点前后地指针信息，分别为prev和next，传入头节点
3、将头节点赋值为curr，开始循环处理，将下一个节点指针保存到next变量 next=curr.next
4、将节点指针指向前一个节点prev，curr.next=prev
5、准备处理下一个节点，将curr赋值给prev
6、将下一个节点赋值为curr，接着处理下一个节点
public static ListNode reserse(ListNode head) {
ListNode prev = null;
ListNode next;
ListNode curr = head;
while (curr != null){
//将当前节点未改变前 指向下一节点的信息 保存到next变量
next = curr.next;
//改变当前节点的指针指向， 将节点指针指向前一个节点prev
curr.next = prev;
//节点改变完了，然后把自己变成前一个节点，则将当前节点信息保存到prev变量
prev = curr;
//接着将下一节点赋予当前节点，准备处理下一节点
curr = next;
}
//返回头节点
return prev;
}
完整代码
下列是完整代码，包含测试代码
package com.cys.algorithm;
public class ReverseList {
static class ListNode {
int val;
ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public static ListNode reserse(ListNode head) {
ListNode prev = null;
ListNode next;
ListNode curr = head;
while (curr != null){
//将当前节点未改变前 指向下一节点的信息 保存到next变量
next = curr.next;
//改变当前节点的指针指向， 将节点指针指向前一个节点prev
curr.next = prev;
//节点改变完了，然后把自己变成前一个节点，则将当前节点信息保存到prev变量
prev = curr;
//接着将下一节点赋予当前节点，准备处理下一节点
curr = next;
}
return prev;
}
public static void main(String[] args) {
ListNode node5 = new ListNode(500, null);
ListNode node4 = new ListNode(400, node5);
ListNode node3 = new ListNode(300, node4);
ListNode node2 = new ListNode(200, node3);
ListNode node1 = new ListNode(100, node2);
ListNode prev = reserse(node1);
System.out.println(prev.val);
System.out.println(prev.next.val);
}
}
测试代码运行结果
解法二：递归
递归的思路其实就是把一个大问题分成许多个小问题，然后寻找到解决办法以后，再将方法推广到全局。
步骤
1、通过头部节点，不停地遍历，直到next指针指向为null，找到最后一个元素
2、如果遇到最后一个元素，则返回。接着将最后一个元素指向倒数第二个元素，并且将倒数第二个元素的指向替换成null，然后继续返回，以此类推
完整代码
下列是完整代码，包含测试代码
package com.cys.algorithm;
public class ReverseList {
static class ListNode {
int val;
ListNode next;
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public static ListNode reserse(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode newHead = reserse1(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static void main(String[] args) {
ListNode node5 = new ListNode(500, null);
ListNode node4 = new ListNode(400, node5);
ListNode node3 = new ListNode(300, node4);
ListNode node2 = new ListNode(200, node3);
ListNode node1 = new ListNode(100, node2);
ListNode prev = reserse(node1);
System.out.println(prev.val);
System.out.println(prev.next.val);
}
}
测试代码运行结果
原文地址：https://blog.csdn.net/qq_32590535/article/details/142690231
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！