这篇关于leetcode算法资料的点评文章展示了编程中一个基本而重要的问题：单链表的反转，文章仔细地介绍了两种常用的方法——迭代和递归，在迭代法中，文档逐步指导读者通过状态变化来实现链表的翻转，详细说明如何使用三个指针：prev、curr和next来逐步遍历并反转链表，在解释递归法时，文档则将问题分解为子问题，便于理解如何从底向上解决链表反转的问题，附带的代码实例为理解算法提供了具体且实际的学习材料，帮助读者更好地把握问题的解决思路，整个文档既适合初学者理解基本概念，也适合进阶读者复习和深化理论知识，是一份内容全面、解释清晰的学习资料。
反转链表
反转一个单链表
输入: 1->2->3->4->5 输出: 5->4->3->2->1
解法1：迭代，重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态、每次处理都会改变状态、直至到达最终状态从前往后遍历链表，将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr，处理完后要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next
1、将下一个节点指针保存到next变量 next = curr.next
2、将下一个节点的指针指向prev，curr.next = prev
3、准备处理下一个节点，将curr赋值给prev
4、将下一个节点赋值为curr，处理一个节点
解法2：递归：以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr将所有的小问题解决，大问题即解决只需每个元素都执行curr.next.next = curr，curr.next = null两个步骤即可
为了保证链不断，必须从最后一个元素开始
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 iterate(ListNode head){
ListNode prev = null,curr,next;
curr = head;
while(curr != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static ListNode recursion(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = recursion(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static void main(String[] args) {
ListNode node5 = new ListNode(5,null);
ListNode node4 = new ListNode(4,node5);
ListNode node3 = new ListNode(3,node4);
ListNode node2 = new ListNode(2,node3);
ListNode node1 = new ListNode(1,node2);
//ListNode node = iterate(node1);
ListNode node_1 = recursion(node1);
System.out.println(node_1);
}
}
