Ruoduan' Blog

这是我参与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` ，请你删除所有重复的元素，使每个元素 **只出现一次** 。

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

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

示例2：

输入：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)的复杂度。本文将讲解单向链表和双向链表，其中双向链表会给出部分关键代码实现。

1. 单向链表

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

2. 双向链表

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