反转一个单链表。
Reverse a singly linked list.
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
Follow up:
A linked 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