LeetCodeJava刷题笔记—206.反转链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

该题在国内的常见算法面试题的出现次数中排第一，递归和非递归这两种方式都一定要掌握。

思路就是交换两个相邻节点的引用关系即可，使用双指针或者递归操作都可以实现，比较简单。注意理解递归的实现，我们返回的是链表的最后一个节点，也就是反转链表的头节点，都是在每次递归返回之后。

/**
* 206. 反转链表
* 反转一个单链表。
* https://leetcode-cn.com/problems/reverse-linked-list/
* 简单
*/
public class LeetCode206 {
/**
* 双指针
*/
public ListNode reverseList(ListNode head) {
//前驱
ListNode pre = null;
while (head != null) {
ListNode next = head.next;
//反转head和pre的关系
head.next = pre;
pre = head;
head = next;
}
return pre;
}
/**
* 递归
*/
public ListNode reverseList1(ListNode head) {
if (head == null || head.next == null) {
//递归到最深入之后从这里开始返回
return head;
}
ListNode next = reverseList1(head.next);
//递归方法返回后执行的步骤，反转引用关系
head.next.next = head;
head.next = null;
//返回之前链表的最后一个节点，也就是反转链表的头节点
return next;
}
public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}