206 反转链表
01
题目信息
题目地址： https://leetcode-cn.com/problems/reverse-linked-list/submissions/
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
02
解法一：迭代
反转一个链表和数组是不一样的，因为不能任意取值，只能说按照next的顺序依次往后放。那么把一个节点往后放的过程就是一次迭代
我们要迭代的有两个值，第一个不用说是当前节点cur每次迭代完它要换成原链表的下一个，第二个是转换过去的next，它是上一个当前节点。
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode next = null;
while( cur != null){
//记住原链表的下一个
ListNode temp = cur.next;
//设下next
cur.next = next;
//更新next与cur
next = cur;
cur = temp;
}
return next;
}
03
解法二：递归
有了这样一个迭代，我们可以去转一下递归。在迭代当中我们去设置了头结点的next为空，之后的next都是推导的，反过来它是我们的递归出口
我们通过reverseListc传入头结点，完成整个链表的反转。如果我们传入头结点的next呢，那么就从图中值为4的节点开始反转得到如下图，最终要实现真正的反转把4节点指向5节点并且5节点指向null。
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null) {
return head;
}
ListNode cur = reverseList(head.next);
//最后操作 4指向5，且5指向null
head.next.next = head;
head.next = null;
return cur;
}
04
解法三：栈
解这一题栈也是可以用，我们迭代顺着从头结点开始，把自己作为下一个被指向。如果倒着取先从最后节点开始把它的next指向前一个节点。但是对于这个单向链表找下一个next就可以取到，但找前一个取不到。
public ListNode reverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
//依次入栈
while (head != null) {
stack.push(head);
head = head.next;
}
if (stack.isEmpty()) return null;
ListNode newHead = stack.pop();
ListNode cur = newHead;
//依次出栈，next为下一个
while (!stack.isEmpty()) {
ListNode temp = stack.pop();
cur.next = temp;
cur = cur.next;
}
//处理最后一个next为null,否则成环
cur.next = null;
return newHead;
}
05
总结
解法二关于递归的改造作为算法学习还是可以多练习的，解法一正向遍历+过程反向（每个把自己作为后一个也就是下一个在前面）解法三反向遍历+过程正向（每个都是前一个它的next就是下一个），总体来说解法一最优，解法二与三练习其他数据结构以及其他算法思想扩展思路
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录