Leetcode 分类刷题 —— 链表类（Linked List）
1、题目
Leetcode 206. Reverse Linked List
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
2、思路
迭代法：从前往后遍历，将当前节点指向它前面的节点
递归法：递归调用，使得下一个节点指向前一个节点
3、Java 代码
public class LeetCode_206_Solution {
/**
* 迭代法
* 1 -> 2 -> 3 -> 4 -> null
* null <- 1 <- 2 <- 3 <- 4
*/
public static ListNode reverseListIterative(ListNode head) {
//前指针节点、当前指针节点
ListNode prev = null;
ListNode curr = head;
//每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
while (curr != null) {
//临时节点，暂存当前节点的下一节点，用于后移
ListNode nextTemp = curr.next;
//将当前节点指向它前面的节点
curr.next = prev;
//前指针后移
prev = curr;
//当前指针后移
curr = nextTemp;
}
return prev;
}
/**
* 递归法
* 1 -> 2 -> 3 -> 4 -> null
* 1 -> 2 -> 3 <- 4
* 1 -> 2 <- 3 <- 4
*/
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//前指针节点head是3；当前指针节点cur是4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
}
