前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode笔记 | 链表(ing)

LeetCode笔记 | 链表(ing)

作者头像
凌川江雪
发布2019-10-24 10:53:45
4540
发布2019-10-24 10:53:45
举报
文章被收录于专栏:李蔚蓬的专栏
@1:反转一个单链表: https://leetcode-cn.com/problems/reverse-linked-list/

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

示例:

代码语言:javascript
复制
输入: 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记录下来;

执行草图:

代码:

代码语言:javascript
复制
/**
 * 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;  //反转指向

代码:

代码语言:javascript
复制
/**
 * 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

代码语言:javascript
复制
/**
 * 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.双指针:

代码语言:javascript
复制
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/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.10.23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • @1:反转一个单链表: https://leetcode-cn.com/problems/reverse-linked-list/
  • 解法1:迭代法( 记录 》反转 》后移 》后移 )
  • 解法2:递归
  • @2:两两交换链表中的节点:https://leetcode-cn.com/problems/swap-nodes-in-pairs/
  • @3:判断链表是否有环:https://leetcode-cn.com/problems/linked-list-cycle/
  • @4:环形链表:https://leetcode-cn.com/problems/linked-list-cycle-ii/
  • @5:每 k 个节点一组翻转链表:https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档