专栏首页李蔚蓬的专栏LeetCode笔记 | 链表(ing)

LeetCode笔记 | 链表(ing)

@1:反转一个单链表: https://leetcode-cn.com/problems/reverse-linked-list/

题目描述: 反转一个单链表。

示例:

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

#解法参考1# #解法参考2#

解法1:迭代法( 记录 》反转 》后移 》后移 )

记录now.next,反转now.next, 后移prev,后移now;

  • now 代表当前节点;
  • 原前驱、原后继、原方向的“原”,指“反转前”;
  • 线性记录特性  “精兵未动,粮草先行” : 如下思路的1、 3两步, 都是为了2、 4两步执行之后,有用信息不丢失; . 想要改变now的后继,先用nextnow原后继记录下来; 想要改变now,先用prev记录下来;

执行草图:

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode now = head;
    while (now != null) {
      ListNode next = now.next;    //next 指向now.next
      now.next = prev;      //now.next 指向prev
      prev = now;
      now = next;
    }

    return prev;
    }
}

解法思路如下:

  • 首先,ListNode head把源节点的头结点传进来;
  • 循环中四行代码,每一行的右边都是下一行的左边, 即改动前先存储(谋定而后动,重要思想!!!!), 环环相扣,安全可靠;
  1. 记录now原后继now.next(因为下一步now.next就要改指向实现反转了): 先将 当前节点now反转前的下一个节点now.next 纪录下来,即ListNode next = now.next; 记录下来的原因是最后第四行要用, 让本轮的now结点能往后移动;
  2. now后继指向原前驱(核心:方向反转): 然后让当前节点反转前的下一个节点的 “指针”now.next置为反转前的上一节点prev,即now.next = prev;
  3. 原前驱后移(基于原方向): 再将当前节点纪录下来,即原前驱后移,prev = now;
  4. now后移: 再让反转前当前节点的下一节点next变为当前节点now;即now = next; now != null即next不为空,表示链表还有节点未处理, 最后now == null,即链表已尽, 此时,next = now = 表尾往后一个“节点”(null) prev指向反转前最后一个节点, 也即反转后第一个节点; 跳出while循环, 所以最后return prev;

运行效果:


解法2:递归

思路如下: 0.利用递归首先找到单链表的最后一个节点; 最后一个节点存储在re里面, re在找到最后一个节点时被赋值且其永远为最后一个节点的值,保持不变; 从找到最后一个节点开始, 从最后往前的方向,每一层递归反转一对节点 / 一个指向;

  1. if 判断,判断是否是空链表(head == null ||)或者是否是链表的最后一个节点(递归终止条件);
  2. 配置好nextnext = head.next;
  3. 剪短原方向:head.next = null;
  4. next丢进递归; 找到最后一个节点的时候会return回来;
  5. 反转一对节点 / 一个方向:next.next = head; 6.返回

核心同样是四行代码,(可以结合运行草图理解) 前两行不断剪除原来的指向 ListNode next = head.next;  //next 指向head.next head.next = null;  //剪除原来的指向 ListNode re = reverseList(next);  //递归找到末节点,记录下来付给re next.next = head;  //反转指向

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    if(head == null || head.next==null)return head;
    ListNode next = head.next;
    head.next = null;
    ListNode re = reverseList(next);
    next.next = head;
    return re;
    }
}

运行草图:

Leetcode提交结果:

注意: 要if判断中要加上head == null ||,防止输出空链表的情况; 否则会报空指针的错:java.lang.NullPointerException


@2:两两交换链表中的节点:https://leetcode-cn.com/problems/swap-nodes-in-pairs/
@3:判断链表是否有环:https://leetcode-cn.com/problems/linked-list-cycle/

1.哈希表 while(head != null)判断是否为表尾; nodes.add(head);如果新节点没有包含,吃进去,一直吃; 终焉两种情况, 2.1. 无环,直到head == null还没重复,false 2.2. 有环,if(nodes.contains(head))直到加到重复的,true

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodes = new HashSet<>();
        while(head != null){
            if(nodes.contains(head))
                return true;
            else 
                nodes.add(head);

            head = head.next;
        }
        return false;
    }
}

复杂度分析

时间复杂度:O(n)O(n),对于含有 nn 个元素的链表,我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1)O(1) 的时间。

空间复杂度:O(n)O(n),空间取决于添加到哈希表中的元素数目,最多可以添加 nn 个元素。

2.双指针:

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}
  1. 空链表 head == null , 一节点链表 head.next == null , 无环 if (head == null || head.next == null) { return false; }
  2. 初始化,快前慢后 ListNode slow = head; ListNode fast = head.next;
  3. 没有追上,就一直跑 while (slow != fast) ... slow = slow.next; fast = fast.next.next;

终焉两种情况: 3.1. 有环,迟早追上 slow == fast 跳出循环,true;

3.2. 无环,快针迟早到链尾,flase if (fast == null || fast.next == null) { return false; }

  • fast == null 跑过头了到尾结点的next;
  • fast.next == null 刚刚好跑到尾结点

复杂度分析

时间复杂度:O(n)O(n),让我们将 nn 设为链表中结点的总数。为了分析时间复杂度,我们分别考虑下面两种情况。

链表中不存在环: 快指针将会首先到达尾部,其时间取决于列表的长度,也就是 O(n)O(n)。

链表中存在环: 我们将慢指针的移动过程划分为两个阶段:非环部分与环形部分:

慢指针在走完非环部分阶段后将进入环形部分:此时,快指针已经进入环中 \text{迭代次数} = \text{非环部分长度} = N迭代次数=非环部分长度=N

两个指针都在环形区域中:考虑两个在环形赛道上的运动员 - 快跑者每次移动两步而慢跑者每次只移动一步。其速度的差值为 1,因此需要经过 \dfrac{\text{二者之间距离}}{\text{速度差值}} 速度差值 二者之间距离 ​ 次循环后,快跑者可以追上慢跑者。这个距离几乎就是 "\text{环形部分长度 K}环形部分长度 K" 且速度差值为 1,我们得出这样的结论 \text{迭代次数} = \text{近似于}迭代次数=近似于 "\text{环形部分长度 K}环形部分长度 K".

因此,在最糟糕的情形下,时间复杂度为 O(N+K)O(N+K),也就是 O(n)O(n)。

空间复杂度:O(1)O(1),我们只使用了慢指针和快指针两个结点,所以空间复杂度为 O(1)O(1)。

@4:环形链表:https://leetcode-cn.com/problems/linked-list-cycle-ii/
@5:每 k 个节点一组翻转链表:https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • vue学习笔记2

    概念:Vue.js 允许你自定义过滤器,可被用作一些常见的文本格式化。过滤器可以用在两个地方:mustache 插值和 v-bind 表达式。过滤器应该被添加在...

    用户6362579
  • oracle--单行函数和多行函数

    eadela
  • 一起学Rust-理解所有权

    原问题是这样的: &str 类型通过mem::size_of::<&str>()进行打印内存,始终为16字节。(这里不严谨了,应该是在64位机器上是16...

    MikeLoveRust
  • 快速调用复杂命令,还支持中文注释,命令行备忘工具navi上线两天就火了

    但是,命令的帮助文档往往内容太太太太多了,在里面找到自己关心的部分实在太难了。查找出来的方法也不能直接使用,还需要手动粘贴下来。

    量子位
  • python语法学习记录

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    云雀叫了一整天
  • 04.Django基础四之模板系统

      当模版引擎遇到一个变量,它将计算这个变量,然后用结果替换掉它本身。 变量的命名包括任何字母数字以及下划线 ("_")的组合。 变量名称中不能有空格或标点符号...

    changxin7
  • 条件竞争(Race condition)漏洞挖掘技巧及实战案例全汇总

    条件竞争漏洞(Race condition)官方概念是“发生在多个线程同时访问同一个共享代码、变量、文件等没有进行锁操作或者同步操作的场景中。” 这个漏洞存在于...

    Jayway
  • pwnable-Col

    注意:必须是小端格式 ‘\xC8\xCE\xC5\x06’ * 4 加上 \xCC\xCE\xC5\x06 刚好是 0x21DD09EC,所以利用成功。

    天钧
  • 多进程、多线程与协程

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    星辉
  • 一起学Rust-实战leetcode(三)

    之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。

    MikeLoveRust

扫码关注云+社区

领取腾讯云代金券