TypeScript算法题实战——链表篇(链表的设计、反转、两两交换、删除、相交和环形链表)

举报
中杯可乐多加冰 发表于 2022/11/22 16:09:49 2022/11/22
【摘要】 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思),链表的类型有单链表、双链表、循环链表。本系列博文将通过一些力扣算法题目,边学习TypeScipt边实战算法,这篇将通过一些经典算法题熟悉TS语言链表的一些基本操作。(部分算法思想参考于程序员Carl:代码随想录)@TOC 一、...

链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思),链表的类型有单链表、双链表、循环链表。

本系列博文将通过一些力扣算法题目,边学习TypeScipt边实战算法,这篇将通过一些经典算法题熟悉TS语言链表的一些基本操作。(部分算法思想参考于程序员Carl:代码随想录

@TOC

一、链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域

链表包括val和next,其中next是ListNode|null类型,next指向的是下一个节点,为ListNode类设计一个构造函数constructor,如下所示:

class ListNode {
    public val: number;
    public next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

二、移除链表元素

2.1、题目描述

力扣链接:https://leetcode.cn/problems/remove-linked-list-elements/
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

2.2、示例

在这里插入图片描述输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

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

示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]

2.3、题解

function removeElements(head: ListNode | null, val: number): ListNode | null {
    while(head != null && head.val == val)
        head = head.next;
    if(head == null)
        return head;
    let pre: ListNode = head;
    while(pre.next!=null){
        let next: ListNode|null = pre.next;
        if(next.val == val){
            pre.next = next.next;
        }
        else
            pre = pre.next;
    }
    return head;
};

三、设计链表

3.1、题目描述

力扣链接:https://leetcode.cn/problems/design-linked-list/
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:valnextval 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能:

get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

3.2、示例

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

3.3、题解

  1. MyLinkedList,有两个哨兵,一个指向头结点,一个指向尾结点;
  2. 需要额外构造一个getnode,用于寻找下标为index的ListNode节点;
  3. addAtHead:首先新建一个结点,结点的val等于val,结点的next指向原链表头结点,然后将this.head指向这个新结点;
  4. addAtTail:首先新建一个结点,将原链表的尾结点的next指向该结点,然后将该结点作为尾结点;
  5. addAtIndex:使用getnode函数找到index的前一个结点curNode,然后构造一个新的listNode结点node,结点node的val为val,结点node的next指向刚刚找到的结点curNode的next,然后将curNode结点的next置为node;
  6. deleteAtIndex:首先处理下index=0,需要删除头结点的情况,若不是index=0,然后使用getnode找到该index下标结点curNode,将curNode的next设置为curNode.next.next,最后处理一下如果index=size-1,需要删除尾结点的情况(因为要重新设置tail)。
// class ListNode {
//     public val: number;
//     public next: ListNode | null;
//     constructor(val?: number, next?: ListNode | null) {
//         this.val = val === undefined ? 0 : val;
//         this.next = next === undefined ? null : next;
//     }
// }

class MyLinkedList {
    private size: number;
    private head: ListNode | null; // 指向头结点
    private tail: ListNode | null; // 指向尾结点
    constructor() {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    getNode(index: number): ListNode{
        let curNode: ListNode = new ListNode(-1, this.head);
        for(let i = 0; i <= index; i++){
            curNode = curNode.next;
        }
        return curNode;
    }
    get(index: number): number {
        if(index < 0)
            return -1;
        if(index >= this.size)
            return -1;
        let curNode: ListNode = new ListNode(-1, this.head);
        for(let i = 0; i <= index; i++){
            curNode = curNode.next;
        }
        return curNode.val;
    }

    addAtHead(val: number): void { // 在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
        let node: ListNode = new ListNode(val, this.head);
        this.head = node;
        if(!this.tail)
            this.tail = node;
        this.size ++;
    }

    addAtTail(val: number): void { //在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
        let node: ListNode = new ListNode(val, null);
        if(this.tail)
            this.tail.next = node;
        else
            this.head = node;
        this.tail = node;
        this.size ++;
    }

    addAtIndex(index: number, val: number): void { //在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
        if(index <= 0){
            this.addAtHead(val);
            return;
        }    
        if(index === this.size){
            this.addAtTail(val);
            return;
        }
        if(index > this.size)
            return;
        
        let curNode: ListNode = this.getNode(index - 1);
        let node: ListNode = new ListNode(val, curNode.next);
        curNode.next = node;
        this.size++;
    }

    deleteAtIndex(index: number): void {//如果索引 index 有效,则删除链表中的第 index 个节点。
        if (index < 0 || index >= this.size) {
            return;
        }
        // 处理头节点
        if (index === 0) {
            this.head = this.head!.next;
            // 如果链表中只有一个元素,删除头节点后,需要处理尾节点
            if (index === this.size - 1) {
                this.tail = null
            }
            this.size--;
            return;
        }
        // 索引有效
        let curNode: ListNode = this.getNode(index - 1);
        curNode.next = curNode.next!.next;
        // 处理尾节点
        if (index === this.size - 1) {
            this.tail = curNode;
        }
        this.size--;
        }
};

四、反转链表

4.1、题目描述

力扣链接:https://leetcode.cn/problems/reverse-linked-list/
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

4.2、示例

在这里插入图片描述

4.3、题解

使用双指针法(一个head,一个cur),要注意额外使用一个temp把 cur->next 节点保存一下

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function reverseList(head: ListNode | null): ListNode | null {
    if(head == null)
        return null;
    // 双指针法 要注意把 cur->next 节点用tmp指针保存一下
    let cur: ListNode = null;
    let temp: ListNode = null;
    while(head){
        temp = head.next;
        head.next = cur;
        cur = head;
        head = temp;
    }
    return cur;
};

使用递归法,其实依旧也是使用的双指针法。

 function reverseList(head: ListNode | null): ListNode | null {
     if(head == null)
        return null;
    function rever(pre: ListNode | null, cur: ListNode | null): ListNode | null{
        if(cur == null)
            return pre;
        let temp: ListNode | null = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
        return rever(pre, cur);
    }
     return rever(null, head);
 };

五、两两交换链表中的节点

5.1、题目描述

力扣链接:https://leetcode.cn/problems/swap-nodes-in-pairs/
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

5.2、示例

在这里插入图片描述

5.3、题解

使用模拟法,首先创建一个虚拟头结点指向head,这样一方面可以保存好链表的头,另一方面也更好操作。
从开始看不太好理解,我们从中间开始看,首先把1 2 3 4链表变成 2 1 3 4,然后我们需要翻转第二次即 2 1 3 4变为 2 1 4 3,要做三件事情,1.next=4;3.next=4.next;4.next =3;
变换之后,再进行第三次的翻转、第四次、…直到结束(循环和递归都可以实现)

实现上,使用三个指针,pre、head、tail来做,具体如下:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function swapPairs(head: ListNode | null): ListNode | null {
    if(head ===null || head.next === null)
        return head;
    let virNode: ListNode = new ListNode(-1, head); //创建一个虚拟头结点
    let preNode: ListNode = virNode;
    while(head != null && head.next !=null){
        let tailNode: ListNode = head.next;
        preNode.next = tailNode; // 1.next=4
        head.next = tailNode.next; // 3.next=4.next
        tailNode.next = head; // 4.next=3

        preNode = head;
        head = head.next;
    }
    return virNode.next;
};

官方递归法:
head 表示原始链表的头节点,新的链表的第二个节点,用 newHead 表示新的链表的头节点,原始链表的第二个节点,则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next),表示将其余节点进行两两交换,交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head,即完成了所有节点的交换。最后返回新的链表的头节点 newHead

可以看到递归法把链表分成两个部分,前面两个节点和后面其他的节点,我们以第一次翻转开始模拟,要做的步骤是:newhead指向当前第二个节点,head指向当前第一个节点,head.next指向后面的链表,newhead.next指向head,然后进入下一次翻转递归,下一次递归就不用看前面的节点了,返回值为翻转后的当前子链表的头结点。

function swapPairs(head: ListNode | null): ListNode | null {
    if (head === null|| head.next === null) {
        return head;
    }
    let newHead: ListNode = head.next; 
    head.next = swapPairs(newHead.next); 
    newHead.next = head; //
    return newHead;
};

六、删除链表的倒数第 N 个结点

6.1、题目描述

力扣链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
给你一个链表,删除链表的倒数n 个结点,并且返回链表的头结点。

6.2、示例

在这里插入图片描述

6.3、题解

使用两个指针pre和last,异步启动。让last先行,pre后行,last = last.next,当last走了n步时,pre就可以开始走了,这样当last走到末尾时,pre刚好就是倒数第几个。
这样就实现一次遍历,达到效果。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let virNode: ListNode = new ListNode(-1,head);
    let preNode: ListNode = virNode;
    let lastNode: ListNode = new ListNode(-1, head);
    while(lastNode != null && lastNode.next != null){
        if(n == 0)
            preNode = preNode.next;
        else
            n--;
        lastNode = lastNode.next;
    }
    preNode.next = preNode.next.next;
    return virNode.next;
};

七、链表相交

7.1、题目描述

力扣链接:https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
在这里插入图片描述

7.2、示例

在这里插入图片描述

7.3、题解

两次寻找A==B的点,当A访问到尾部后,将其重新置为B的头部,B访问到尾部后,将其重新置为A的头部,这样找就补足了A和B的长度差,第二次A和B就会相遇。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  	let A: ListNode | null = headA;
  	let B: ListNode | null = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
};

八、环形链表

8.1、题目描述

力扣链接:https://leetcode.cn/problems/linked-list-cycle-ii/

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改链表

8.2、示例

在这里插入图片描述

8.3、题解

使用快慢指针法,快指针一次走两格,慢指针一次走一格。
主要需要解决两个问题:

  1. 为何慢指针第一圈走不完一定会和快指针相遇: 首先,第一步,快指针先进入环 第二步:当慢指针刚到达环的入口时,快指针此时在环中的某个位置(也可能此时相遇) 第三步:设此时快指针和慢指针距离为x,若在第二步相遇,则x = 0; 第四步:设环的周长为n,那么看成快指针追赶慢指针,需要追赶n-x; 第五步:快指针每次都追赶慢指针1个单位,设慢指针速度1/s,快指针2/s,那么追赶需要(n-x)s 第六步:在n-x秒内,慢指针走了n-x单位,因为x>=0,则慢指针走的路程小于等于n,即走不完一圈就和快指针相遇。
  2. 为何 slow(新的slow) 和 fast 第二次相遇时,相遇的节点即为环路的开始点。可以看这篇题解:https://leetcode.cn/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let slowNode: ListNode | null = head,
        fastNode: ListNode | null = head;
    while(fastNode !== null && fastNode.next !== null){
        slowNode = slowNode.next;
        fastNode = fastNode.next.next;
        if(slowNode === fastNode){
            slowNode = head;
            while(slowNode !== fastNode){
                slowNode = slowNode.next;
                fastNode = fastNode.next;
            }
            return slowNode;
        }
    }
    return null;
};

最后

💖 个人简介:人工智能领域研究生,目前主攻文本生成图像(text to image)方向

📝 关注我:中杯可乐多加冰

🔥 限时免费订阅:TypeScript实战

🎉 支持我:点赞👍+收藏⭐️+留言📝

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。