原文：反转链表

目录

1、题目：206.反转链表

2、题解

---

学习笔记，侵删！

1、题目：206.反转链表

反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

2、题解

只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:

之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

// 双指针
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;ListNode temp = null;while (cur != null) {temp = cur.next;// 保存下一个节点cur.next = prev;prev = cur;cur = temp;}return prev;}
}

// 递归 
class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur == null) {return prev;}ListNode temp = null;temp = cur.next;// 先保存下一个节点cur.next = prev;// 反转// 更新prev、cur位置// prev = cur;// cur = temp;return reverse(cur, temp);}
}

/ 从后向前递归
class Solution {ListNode reverseList(ListNode head) {// 边缘条件判断if(head == null) return null;if (head.next == null) return head;// 递归调用，翻转第二个节点开始往后的链表ListNode last = reverseList(head.next);// 翻转头节点与第二个节点的指向head.next.next = head;// 此时的 head 节点为尾节点，next 需要指向 NULLhead.next = null;return last;} 
}