LeetCode 206：反转链表 Reverse Linked List

反转一个单链表。

Reverse a singly ed list.

示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

Follow up:

A ed list can be reversed either iteratively or recursively. Could you implement both?

解题思路：

每次遍历到最后一位取节点这种方法就算了时间复杂度太高。如题目进阶要求的两种方法，迭代和递归：

迭代：

每次分出来一个节点把节点作为头节点添加到新链表上：

原链表：1->2->3->4->5

分离第一个节点作为头节点添加到新链表：1 原链表：2->3->4->5

分离下一个节点作为头节点添加到新链表：2->1 原链表：3->4->5

分离下一个节点作为头节点添加到新链表：3->2->1 原链表：4->5

分离下一个节点作为头节点添加到新链表：4->3->2->1 原链表：5

分离下一个节点作为头节点添加到新链表：5->4->3->2->1 原链表：null

Java：

class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null) return head;        ListNode pre = null;        ListNode tmp = null;        while (head != null) {            tmp = head.next;//tmp暂存当前节点的下一个节点            head.next = pre;//当前节点下一个指向pre            pre = head;//刷新pre            head = tmp;//刷新当前节点为tmp        }        return pre;    }}

Python3：

class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        pre,tmp=None,None        while(head):            tmp=head.next            head.next=pre            pre=head            head=tmp        return pre

递归：

其实就是用递归完成栈的功能：先进后出

基线条件为遇到空节点（到链表末尾），返回对象为链表的最后一个节点，在递归函数中传递一直不变。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。

原链表：1->2->3->4->5

递归到最后一层时遇到null节点返回尾节点5

回到上一层递归 分离节点 5 作为新链表的尾节点：5，置空原本5节点，原链表1->2->3->4->null

回到上一层递归 分离节点 4 作为新链表的尾节点：5->4，置空原本4节点，原链表1->2->3->null

回到上一层递归 分离节点 3 作为新链表的尾节点：5->4->3，置空原本3节点，原链表1->2->null

回到上一层递归 分离节点 2 作为新链表的尾节点：5->4->3->2，置空原本2节点，原链表1->null

回到上一层递归 分离节点 1 作为新链表的尾节点：5->4->3->2->1，置空原本1节点，原链表null

Java：

class Solution {    public ListNode reverseList(ListNode head) {        //基线条件        if (head == null || head.next == null) return head;        //递归        ListNode tmp = head.next;//暂存头节点的下一个节点        ListNode pre = reverseList(head.next);//递归调用该函数，pre为返回的新链表的头节点，原链表的最后一个节点，无论递归多少层该返回值一直传递不变        tmp.next = head;//暂存的下一个节点指向传入节点        head.next = null;//下一个节点即原本指向tmp的节点 置空        return pre;    }}

Python3：

class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        tmp = head.next        pre = self.reverseList(head.next)        tmp.next = head        head.next = None        return pre

欢迎关注公.众号一起刷题：爱写Bug