LeetCode206题-翻转链表
零 题目分析
Given the head of a singly linked list, reverse the list, and return the reversed list.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一 题解思路
对于初始链表：1–>2–>3–>4–>5–>NULL，我们需要获取一个5–>4–>..1->NULL的链表。考虑通过栈这种数据结构，在不考虑通过借助栈或其它数据结构的情形下，让某个节点指向其前一个节点，这样实现反转的思路。可是，没有指向前1个节点的指针，我们人为构建出来1个pre节点，让它指向当前节点的前一个节点，curr指向当前节点，next指向当前节点的下一个节点。
二 代码实现
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev=null;
ListNode curr=head;
while(curr!=null){
ListNode next=curr.next;
//当前节点的下一个指向前一个节点，实现了当前节点和它之前的节点的反转
curr.next=prev;
//令其前一个节点指向当前节点，
prev=curr;
//当前节点指向下一个节点
curr=next;
}
// 最后返回prev，而不是curr节点，因为，最后curr一定是等于NULL时，就退出while循环的
return prev;
}
}三 递归实现
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//1 先写出基本情况的代码，不依赖于其它情况都能计算出来的结果
//如果链表为空，或者链表只有1个元素，那么翻转之后，还是它自身
if(head==null||head.next==null){
return head;
}
//2朝着正确的方向，将问题简化1步的方向前进，假定头节点已经翻转，接下来要翻转除头节点之外的链表
ListNode retNode=reverseList(head.next);
//3返回的retNode是除头节点之外的所有节点，且已经翻转之后的链表的头节点
//1-->2-->3--4>-->5
//1-->2<--3<--4<--5
//这里的retNode其实就是指向了5.我们的head还是指向了1，且head.next=2
//3 我们让head.next.next=head。其实就是让2-->1。仔细体会，这是神来之笔的一句代码。
head.next.next=head;
//4最后让head.next=null，即让1指向NULL，1充当链表的最后1个节点
head.next=null;
retrun retNode;
}
}
