首页 > 编程语言 >每日算法随笔:反转链表

每日算法随笔:反转链表

时间:2024-09-10 15:14:31浏览次数:10  
标签:head null curr next 链表 算法 prev 随笔

题解:反转链表

这道题目要求我们将一个单链表进行反转,返回反转后的链表。链表的反转可以通过 迭代递归 两种方法来实现。下面我们将详细解释这两种方法,并通过例子演示每一步的变化过程。

方法一:迭代法

思路

  • 我们用三个指针来完成链表的反转:prev 表示前一个节点,curr 表示当前节点,next 表示下一个节点。
  • 通过不断将当前节点的 next 指针指向 prev,实现链表的逐步反转。

迭代的步骤

  1. 初始化 prev = nullcurr = head,然后开始遍历链表。
  2. 在每次迭代中,先用 next 保存 curr.next,避免链表断开。
  3. curr.next 指向 prev,反转当前节点的指向。
  4. prev 移动到 curr,然后将 curr 移动到 next,继续下一次迭代。
  5. currnull 时,链表反转完成,prev 就是新的头节点。

代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // 保存下一个节点
            curr.next = prev; // 反转当前节点的指向
            prev = curr; // 将 prev 前移
            curr = next; // 将 curr 前移
        }
        return prev; // prev 成为新链表的头节点
    }
}

例子演示

输入head = [1,2,3,4,5]

  1. 初始状态:

    prev = null
    curr = 1 -> 2 -> 3 -> 4 -> 5
    
  2. 第一步:

    next = 2 -> 3 -> 4 -> 5
    curr.next = prev  // 1 -> null
    prev = 1 -> null
    curr = 2 -> 3 -> 4 -> 5
    
  3. 第二步:

    next = 3 -> 4 -> 5
    curr.next = prev  // 2 -> 1 -> null
    prev = 2 -> 1 -> null
    curr = 3 -> 4 -> 5
    
  4. 第三步:

    next = 4 -> 5
    curr.next = prev  // 3 -> 2 -> 1 -> null
    prev = 3 -> 2 -> 1 -> null
    curr = 4 -> 5
    
  5. 第四步:

    next = 5
    curr.next = prev  // 4 -> 3 -> 2 -> 1 -> null
    prev = 4 -> 3 -> 2 -> 1 -> null
    curr = 5
    
  6. 第五步:

    next = null
    curr.next = prev  // 5 -> 4 -> 3 -> 2 -> 1 -> null
    prev = 5 -> 4 -> 3 -> 2 -> 1 -> null
    curr = null
    

输出[5, 4, 3, 2, 1]

复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的节点数。我们只遍历了链表一次。
  • 空间复杂度:O(1),只用了常数级别的额外空间。

方法二:递归法

思路

  • 我们递归地反转链表的后续部分,直到最后一个节点成为新的头节点。
  • 每次递归返回时,将当前节点的下一个节点的 next 指向自己,同时将自己的 next 置为空,完成反转。

递归步骤

  1. 如果 headnull 或者 head.nextnull,直接返回 head 作为新的头节点(即递归的终止条件)。
  2. 递归反转剩余的链表。
  3. 将当前节点的下一个节点的 next 指向自己,同时将自己的 next 置为空。
  4. 返回新的头节点。

代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; // 递归终止条件
        ListNode newHead = reverseList(head.next); // 反转后续链表
        head.next.next = head; // 将后面的节点指向自己
        head.next = null; // 断开当前节点与后续的连接
        return newHead; // 返回新的头节点
    }
}

例子演示

输入head = [1,2,3,4,5]

  1. 初始递归:

    • reverseList(1) 递归调用 reverseList(2)
  2. 递归到最后一个节点:

    • reverseList(5) 返回 5 作为新头节点。
  3. 逐步反转链表:

    • reverseList(4)

      head = 4 -> 5
      反转后 5 -> 4
      head.next.next = 4
      head.next = null // 4 -> null
      返回 5 -> 4 -> null
      
    • reverseList(3)

      head = 3 -> 4 -> null
      反转后 5 -> 4 -> 3
      head.next.next = 3
      head.next = null
      返回 5 -> 4 -> 3 -> null
      
    • reverseList(2)

      head = 2 -> 3 -> null
      反转后 5 -> 4 -> 3 -> 2
      head.next.next = 2
      head.next = null
      返回 5 -> 4 -> 3 -> 2 -> null
      
    • reverseList(1)

      head = 1 -> 2 -> null
      反转后 5 -> 4 -> 3 -> 2 -> 1
      head.next.next = 1
      head.next = null
      返回 5 -> 4 -> 3 -> 2 -> 1 -> null
      

输出[5, 4, 3, 2, 1]

复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的节点数。递归过程中每个节点只处理一次。
  • 空间复杂度:O(n),递归调用的栈深度为 n

总结:

  • 迭代法:通过三个指针逐步反转链表,时间和空间复杂度都为 O(n) 和 O(1),适合在空间要求较严格的场景下使用。
  • 递归法:利用函数调用栈进行递归,代码简洁直观,但需要 O(n) 的额外空间。

标签:head,null,curr,next,链表,算法,prev,随笔
From: https://www.cnblogs.com/yubaibaibubai/p/18406442

相关文章

  • 【Py/Java/C++三种语言OD独家2024E卷真题】20天拿下华为OD笔试之【回溯】2024E-字符串
    可上欧弟OJ系统练习华子OD、大厂真题绿色聊天软件戳od1441了解算法冲刺训练(备注【CSDN】否则不通过)文章目录相关推荐阅读题目描述与示例题目描述输入描述输出描述示例一输入输出说明示例二输入输出说明解题思路代码pythonjavacpp时空复杂度华为OD算法/大厂面......
  • *Python*机器学习算法——神经网络和深度学习
            神经网络和深度学习是现代机器学习的重要组成部分,它们在图像识别、语音识别、自然语言处理等多个领域取得了显著的成功。本文将详细介绍神经网络和深度学习的基本函数概念,并通过一个简单的例子来展示如何使用Python和Keras库构建一个神经网络模型。1、前置库......
  • 莫队算法
    莫队算法普通莫队形式:给定一个长度为\(n\)的序列,有\(q\)次询问,每次询问给出\(l,r\),问区间\([l,r]\)的答案。要求:询问必须离线,且从区间\([l,r]\)转移到区间\([l+1,r],[l-1,r],[l,r+1],[l,r-1]\)的时间复杂度是\(O(1)\)的。做法:关于\(l\)对询问分块,块长为\(T\),......
  • 聚类算法 0基础小白也能懂(附代码)
    聚类算法0基础小白也能懂(附代码)原文链接啥是聚类算法聚类(Clustering)是最常见的无监督学习算法,它指的是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类......
  • 最长匹配算法
    1、实例2、详解1)确定目的地址:192.168.2.22)查找路由表中:目的网路/掩码第一步:目的地址与掩码进行二进制与运算  11000000101010000000001000000010&11111111111111110000000000000000                         ......
  • 第J3周:DenseNet算法实战与解析(TensorFlow版)
    >-**......
  • Java-实现双向环形链表
            双向链表是一种常用的数据结构,其特点是每个节点不仅包含数据,还持有指向前一个节点和后一个节点的指针。与普通双向链表不同的是,它的哨兵节点的prev指向最后一个元素,而最后一个元素的next指向哨兵。        具体双向普通链表可以参考我的上篇文章,这里......
  • 【Python】排序算法及二叉树讲解(冒泡 选择 插入 二分查找 二叉树的广度优先和三种深
    排序算法​所谓排序,使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作​排序算法,就是如何使得记录按照要求排列的方法​排序算法在很多领域是非常重要​在大量数据的处理方面:一个优秀的算法可以节省大量的资源。​在各个领域中考虑到数据的......
  • [Python手撕]排序链表
    #Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defsortList(self,head:Optional[ListNode])->Optional[ListNode]:def......
  • 【算法题】13.罗马数字转整-力扣(LeetCode)
    【算法题】13.罗马数字转整-力扣(LeetCode)1.题目下方是力扣官方题目的地址13.罗马数字转整数罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D5......