写点什么

[力扣] 剑指 Offer 第二天 - 反转链表

作者:陈明勇
  • 2022-11-16
    广东
  • 本文字数:1089 字

    阅读完需:约 4 分钟

[力扣] 剑指 Offer 第二天 - 反转链表

耐心和持久胜过激烈和狂热。

题目来源

来源:力扣(LeetCode)链接:https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目描述

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例

输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
复制代码

题目分析

第一种做法是使用递归,递归到尾结点时,回溯,将每个节点的 next 指向反转,此时的尾结点就是反转后的头结点。第二种做法是迭代法,也就是双指针法,通过两个指针改变每个节点的指向。

解题思路

递归

链表 n1 → n2 → ··· → nk-1 → nk → nk+1 → nm若想将 nk+1 的下一个节点指向 nk,做法是 nk.next.next = nk,简单解释一下这行代码,nk.next 等于 nk+1,而 nk.next.next = nk+1.nextnk,这样就实现了反转,特别注意的是,需要将某个节点的下一个节点指向空(n.next = null),避免回环,也能达到将尾结点指向空的目的。递归的终止条件是当前节点为空或当前节点的下一个节点为空,反转操作在回溯阶段进行。

迭代(双指针)

遍历链表,在遍历的过程中修改节点的指向,由于需要指向前节点,因此需要定义一个指针,用于保存前节点,改变指向之后,就会造成原本的下一个节点无法找到,因此还需要定义另一个指针,再改变指向之前,保存下一个节点。

代码实现

递归

/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func reverseList(head *ListNode) *ListNode {  if head == nil || head.Next == nil{        return head    }    res := reverseList(head.Next)    head.Next.Next = head    head.Next = nil    return res}
复制代码

执行结果


复杂度分析

时间复杂度:O(N),N 为 链表的长度,递归需要遍历链表一次。空间复杂度:O(N),递归需要 O(N) 的栈空间。

迭代

代码实现

/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func reverseList(head *ListNode) *ListNode {  var pre *ListNode    cur := head    for cur != nil {        next := cur.Next        cur.Next = pre        pre = cur        cur = next    }    return pre}
复制代码

执行结果


复杂度分析

时间复杂度:O(N),N 为链表的长度,需要遍历链表一次。空间复杂度:O(1),没有使用额外的内存空间。

总结

根据执行结果可以看出,递归比非递归慢,原因是每次分配函数内存以及栈都需要时间。


以上是本人的解法,如果对你有帮助,欢迎点赞收藏加关注,如果有错误的地方,欢迎指正!

发布于: 刚刚阅读数: 8
用户头像

陈明勇

关注

一个热爱技术,喜欢专研技术的程序员。 2021-10-20 加入

还未添加个人简介

评论

发布
暂无评论
[力扣] 剑指 Offer 第二天 - 反转链表_Go_陈明勇_InfoQ写作社区