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就是下一个),总体来说解法一最优,解法二与三练习其他数据结构以及其他算法思想扩展思路

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 206. 反转链表

    Michel_Rolle
  • 206. 反转链表

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络...

    lucifer210
  • 206. 反转链表

    CaesarChang张旭
  • Leetcode 206. 反转链表

    遍历链表,以 cur 表示当前节点,以 last 表示上一个节点,将 cur 的 next 指针指向 last 即可。

    zhipingChen
  • LeetCode 206. 反转链表

    freesan44
  • leetcode:206 反转链表

    怎么做? 先定义两个变量,为双向指针。一个指向null,一个head,为什么不是一个为1,一个为2。 因为如果这样输出的怎么有null呢,所以一个为null...

    贵哥的编程之路
  • LeetCode | 206.反转链表

    LeetCode 是著名的练习数据结构与算法的网站,很多学习程序设计的人都在刷上面的题来巩固和提高自己的数据结构以及算法的能力。同时,该网站的很多数据结构及算法...

    码农UP2U
  • LeetCode 图解 | 206.反转链表

    今天分享的题目来源于 LeetCode 上第 206 号问题:反转链表。这道题目经常出现在算法面试中的笔试环节。

    五分钟学算法
  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • LeetCode 每日一题206: 反转链表

    按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.

    benny
  • LeetCode 每日一题206: 反转链表

    按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.

    benny
  • Leetcode刷题 206. 反转链表 递归迭代两种方法实现

    **链接**:https://leetcode-cn.com/problems/reverse-linked-list/

    一只胡说八道的猴子
  • Leetcode刷题 206. 反转链表 递归迭代两种方法实现

    链接:https://leetcode-cn.com/problems/reverse-linked-list/

    一只胡说八道的猴子
  • LeetCode 206题 反转链表(Reverse Linked List)

    题目描述: 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    code随笔
  • LeetCode题组:第206题-反转链表

    K同学啊
  • 链表问题-LeetCode 206、234、160(反转,回文,公共结点)

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

    算法工程师之路
  • [剑指offer] 反转链表

    设置三个指针,head为当前节点,pre为当前节点的前一个节点,next为当前节点的下一个节点,需要pre和next的目的是让当前节点从pre->head->n...

    尾尾部落
  • 反转链表

    在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储...

    木子星兮

扫码关注云+社区

领取腾讯云代金券