一文读懂链表的逆转（迭代法和递归法）--二、递归法
最编程
2024-04-18 15:41:05
...
迭代法的解题思路是：通过循环遍历的方式，使链表的每一个节点和它的下一个节点断开，然后重置其下一个节点。
代码实现：
import lombok.AllArgsConstructor;
import lombok.Data;
@Data
@AllArgsConstructor
public class ListNode {
private int value;
private ListNode next;
/**
* 迭代法
* @param head
* @return
*/
public static ListNode reverseIterate(ListNode head){
ListNode pre = null,cur = head,next = null;
while (null != cur){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public static void main(String[] args) {
ListNode listNode4 = new ListNode(4, null);
ListNode listNode3 = new ListNode(3, listNode4);
ListNode listNode2 = new ListNode(2, listNode3);
ListNode listNode1 = new ListNode(1, listNode2);
System.out.println(reverseIterate(listNode1));
}
}
代码解释：
对于链表中的一个节点(cur)来说，它包含节点的值（value）、其所指向的下一个节点（next）、及指向它的上一个节点（pre）。反转链表就是要把当前节点指向的下一个节点变成指向上一个节点。（链表头没有上一个节点，链表尾下一个节点的指向为空）
next = cur.next; 保留当前节点的下一个节点
cur.next = pre; 重置当前节点的下一个节点为上一个节点
pre = cur; 下次遍历需要用到的上一个节点
cur = next; 下次遍历需要用到的当前节点
其执行过程可以用下图表示：
迭代法的特点是：从前向后节点之间的链接依次断开， 重置每个节点下一个节点的指向。