剑指 Offer 24.反转链表

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 24.反转链表

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

反转一个单链表。

示例:

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

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

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

要想从输入链表:

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

变成输出链表:

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

意味着每个节点的下一节点(next)变成了它的前节点(pre)

那思路就是去遍历整个链表,然后执行把每个节点的下一节点(next)变成它的前节点(pre)这个操作。

2、规律

设置三个节点 precurnext ,其中 pre 为原链表之前的空节点,cur 为原链表的头节点,nextcur 的下一节点:

  • (1)每次查看 cur 节点是否为 NULL ,如果是,则结束循环,获得结果
  • (2)如果 cur 节点不是为 NULL ,则先设置临时变量 nextcur 的下一个节点
  • (3)让 cur的下一个节点变成指向 pre ,而后 pre 移动 curcur移动到 next
  • (4)重复(1)(2)(3)

3、匹配

4、边界

三、动画描述

四、图片描述

剑指 offer 面试题精选图解面试题24.反转链表.002

剑指 offer 面试题精选图解面试题24.反转链表.003

剑指 offer 面试题精选图解面试题24.反转链表.004

剑指 offer 面试题精选图解面试题24.反转链表.005

剑指 offer 面试题精选图解面试题24.反转链表.006

剑指 offer 面试题精选图解面试题24.反转链表.007

剑指 offer 面试题精选图解面试题24.反转链表.008

剑指 offer 面试题精选图解面试题24.反转链表.009

剑指 offer 面试题精选图解面试题24.反转链表.010

剑指 offer 面试题精选图解面试题24.反转链表.011

剑指 offer 面试题精选图解面试题24.反转链表.012

剑指 offer 面试题精选图解面试题24.反转链表.013

剑指 offer 面试题精选图解面试题24.反转链表.014

剑指 offer 面试题精选图解面试题24.反转链表.015

剑指 offer 面试题精选图解面试题24.反转链表.016

剑指 offer 面试题精选图解面试题24.反转链表.017

剑指 offer 面试题精选图解面试题24.反转链表.018

剑指 offer 面试题精选图解面试题24.反转链表.019

剑指 offer 面试题精选图解面试题24.反转链表.020

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public ListNode reverseList(ListNode head) {
        //设置节点 cur 和节点 pre,其中 cur 为原链表的头节点,pre 为原链表之前的空节点
        ListNode cur = head, pre = null;
        // 不断的遍历链表,直到遍历到链表的尾部
        while (cur != null) {
            // 获取的当前节点 cur 的下一个节点
            ListNode next = cur.next;
            // 修改当前节点的下一个节点为 pre
            cur.next = pre;
            // pre 向前移动,变成了 cur
            pre = cur;
            // cur 向前移动,变成了 next
            cur = next;
        }
        // 返回 pre
       return pre;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(1)。

七、相关标签

  • 链表

发表评论

邮箱地址不会被公开。 必填项已用*标注