- 难度：
简单 - 本题涉及算法：
迭代递归 - 思路：
迭代递归 - 类似题型:
题目 206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
方法一 迭代
解题思路
通过迭代 将 1->2->3->4->5->∮ 转换成 ∮<-1<-2<-3<-4<-5
如图执行过程:
python
class Solution(object):
def reverseList(self, head):
# 申请两个链表 一个空链表，一个完整的链表
pre = None
curr = head
while curr:
temp = curr.next
curr.next = pre # 当前链表指向 新链表
pre = curr # 赋值给新链表
curr = temp
return pre
java
class Solution {
public ListNode reverseList(ListNode head) {
// 申请两个链表 一个空链表，一个完整的链表
ListNode pre = null;
ListNode curr = head;
while (curr!=null){
ListNode temp = curr.next;
curr.next = pre; // 当前链表指向 新链表
pre = curr; // 赋值给新链表
curr = temp;
}
return pre;
}
}
迭代升级版
python
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur , prev = head, None
while cur:
cur.next ,prev, cur = prev, cur , cur.next
return prev
递归
解题思路
- 终止条件是当前节点或者下一个节点==null
- 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head
ListNode cur = reverseList(head.next); // 当head=4 head.next->5
if(head==null || head.next==null) { // head.next ->null 即 5.next = null
return head; // head = 5
}
- 所以 cul =5
- head.next.next = head; 中head = 4
- 即 4.next.next = 4
- 即 5.next = 4
java
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的下一个是5，下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
}
python
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 递归终止条件是当前为空，或者下一个节点为空
if(head==None or head.next==None):
return head
# 这里的cur就是最后一个节点
cur = self.reverseList(head.next)
# 如果链表是 1->2->3->4->5，那么此时的cur就是5
# 而head是4，head的下一个是5，下下一个是空
# 所以head.next.next 就是5->4
head.next.next = head
# 防止链表循环，需要将head.next设置为空
head.next = None
# 每层递归函数都返回cur，也就是最后一个节点
return cur
方法三 栈
- 通过遍历把链表元素添加到栈内存
- 在把栈里面数据挨个添加到新的链表中
java
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
// 遍历链表到栈内存
Stack<Integer> stack = new Stack<>();
ListNode ans = null;
while (head != null) {
stack.push(head.val);
head = head.next;
}
ListNode reverseListHead = new ListNode(stack.pop()); // 初始化链表首个元素
ListNode tempNode = reverseListHead;
while (!stack.isEmpty()) {
tempNode.next = new ListNode(stack.pop());
tempNode = tempNode.next;
}
return reverseListHead;
}
}
- 如果你觉得本文对你有帮助，请点赞👍支持
- 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出
PREVIOUS213. 打家劫舍 II
NEXT202. 快乐数