3周攻克数据结构[链表篇-2]-一一网

这是我参与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：双指针

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

定义2个指针和寄存器

让第一个头部指向 null，代表最后一个

每次移动2个指针的位置

tmp ：寄存器储蓄下一个链表

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
};
复制代码