专栏首页编程拯救世界图解精选 TOP 面试题 005 | 反转链表之迭代求解

图解精选 TOP 面试题 005 | 反转链表之迭代求解

该系列题目取自 LeetCode 精选 TOP 面试题列表:https://leetcode-cn.com/problemset/top/

题目描述

LeetCode 206. 反转链表:https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

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

进阶:

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

解题思路

链表反转在面试中非常常见,我也在面试中遇到过这道题。在本篇文章中我们先说说如何用迭代法求解该题。

在反转的过程中:

  • 为了反转,我们需要知道节点的上一个节点
  • 为了继续遍历,我们也需要知道节点的下一个节点

因此,在循环迭代节点的过程中需执行如下步骤(设当前节点为 cur):

  1. 保存节点的前一个节点 pre
  2. 保存节点的下一个节点 next
  3. 修改节点的 next 指针,使它指向前一个节点 cur.next = pre

以题目中给出的 1->2->3->4->5->NULL 为例,反转过程如下:

反转链表图解步骤

⚠️ 需要注意的是:

  1. 为了进行下一轮遍历,在修改 next 指针前需要先保存下一个节点
  2. 反转结束后,最终要返回的节点为原链表的最后一个节点

具体实现

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        while head:
            # 获取下一个节点
            next_node = head.next
            # 改变下一个节点
            head.next = pre
            # 修改 pre
            pre = head
            # 修改 head
            head = next_node
        return pre

Go

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

复杂度

  • 时间复杂度
  • 空间复杂度

总结

反转链表的关键在于保存好上一个节点,并处理好 next 指针的修改时机。

关于本题的递归求解的方式,我们下期再聊~

本文分享自微信公众号 - 编程拯救世界(CodeWarrior_),作者:江子抑

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

原始发表时间:2019-12-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图解精选 TOP 面试题 005.1 | 反转链表之递归求解

    在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中,我们介绍了该题的迭代求解法,本篇再说说如何进行递归求解。

    江不知
  • 图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

    本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

    江不知
  • 精选 TOP 面试题 001 | LeetCode 237. 删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    江不知
  • 每天一道剑指offer-反转链表

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • LeetCode 203. Remove Linked List Elements

    ShenduCC
  • C++版 - 剑指offer之面试题37:两个链表的第一个公共结点[LeetCode 160] 解题报告

    提交网址: http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&...

    Enjoy233
  • 剑指offer(5)——从尾到头打印链表

    用代码征服天下
  • ​精益求精单链表归并排序与快速排序

    本节主要阐述自顶向下与自底向上的归并排序,以及改变连接状态与改变节点值的可快速排序。下面来仔细阐述。

    公众号guangcity
  • LeetCode 92. Reverse Linked List II

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

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

    benny

扫码关注云+社区

领取腾讯云代金券