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

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

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

一、链表的定义

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

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

代码语言：javascript复制

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、题解

代码语言：javascript复制

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/ 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，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）。

代码语言：javascript复制

// 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 节点保存一下

代码语言：javascript复制

/**
 * 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;
};

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

代码语言：javascript复制

 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来做，具体如下：

代码语言：javascript复制

/**
 * 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，然后进入下一次翻转递归，下一次递归就不用看前面的节点了，返回值为翻转后的当前子链表的头结点。

代码语言：javascript复制

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刚好就是倒数第几个。 这样就实现一次遍历，达到效果。

代码语言：javascript复制

/**
 * 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/ 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

7.2、示例

7.3、题解

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

代码语言：javascript复制

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-/

代码语言：javascript复制

/**
 * 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;
};

腾讯技术创作特训营S8

0 人点赞