2021 年 08 月 06 日

这是我参与8月更文挑战的第7天,活动详情查看:8月更文挑战

本文题目全部来自 LeetCode

使用 Typescript

本篇文章全部收藏于专栏 3周攻克数据结构-LeetCode

本文所有代码和解题步骤将放置 GitHub仓库

DAY8

1. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

反转链表

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
  • 通用的解题思路:链表的题目通常情况下都是用递归去解决,这道题可以用递归双指针来解决,其实思路都是一样的 看图 👇🏻
反转链表思路

方法1:递归

递归理解起来可能有些难理解,其实他和双指针的做法是一样的,都是把下一指针向后指

function reverseList(head: ListNode | null): ListNode | null {
    // 如果当前链表和下一个链表不存在返回当前 head
    if (head == null || head.next == null) {
        return head;
    }
    // 递归
    const newHead = reverseList(head.next);
    // 让链表指针向后指
    head.next.next = head;
    head.next = null;

    return newHead;
};

方法2:双指针

双指针的代码比较清晰了。

  1. 定义2个指针和寄存器
  2. 让第一个头部 指向 null,代表最后一个
  3. 每次移动2个指针的位置
  4. tmp :寄存器 储蓄下一个 链表
  5. 2个链表交换位置
function reverseList(head: ListNode | null): ListNode | null {
    if(!head || !head.next) return head;

    // 指针 pre 【上一个】
    let pre = null
    // 定义寄存器
    let tmp = null
    // 指针 cur 【下一个】
    let cur = head

    // 移动指针
    while(cur) {
        tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
};

2. 删除排序链表中的重复元素

示例1:

存在一个按升序排列的链表,给你这个链表的头节点 `head` ,请你删除所有重复的元素,使每个元素 **只出现一次** 。

返回同样按升序排列的结果链表。

img

输入:head = [1,1,2]
输出:[1,2]

示例2:

img

输入:head = [1,1,2,3,3]
输出:[1,2,3]

方法1:一次遍历

注意📢:链表是排序好的!

  • 我们只需要遍历一次,不断地和后面的元素做比较,发现相等跳过即可
function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (!head) return head

    let item = head
    
    // 因为是升序的我们可以拿当前的链表不断的和下一个比较,发现重复就跳过
    while (item.next) {
        if (item.val === item.next.val) {
            // 重复,跳过
            item.next = item.next.next;
        } else {
            item = item.next
        }
    }

    return head
};

科普篇

图片文字,均来自网络

  • 链表

    线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表的插入和删除操作可以达到O(1)的复杂度。本文将讲解单向链表和双向链表,其中双向链表会给出部分关键代码实现。

  • 单向链表

    单向链表(单链表)是链表的一种,它由节点组成,每个节点都包含下一个节点的指针,下图就是一个单链表,表头为 空,表头的后继节点是”结点10”(数据为10的结点),“节点10”的后继结点是”节点20”(数据为10的结点),…

image.png

  1. 双向链表

双向链表(双链表)是链表的一种。和单链表一样,双链表也是由节点组成,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

image.png


© 2021, 滇ICP备19003866号本网站版权归本站作者Ruoduan所有原创文章遵循CC BY-SA 4.0授权许可,转载请注明出处