---
title: 链表
description: 
published: true
date: 2024-03-21T11:15:17.596Z
tags: 算法
editor: markdown
dateCreated: 2024-03-21T11:15:17.596Z
---

# 移除链表元素
题意：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：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 输出：[]
```ts
/**
 * 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 removeElements(head: ListNode | null, val: number): ListNode | null {
    let now = head;
    while (now?.next) {
        if (now.next.val === val) {
            now.next = now.next.next
        }else{
            now = now.next
        }
    }
    if (head?.val === val) {
        head = head?.next
    }
    return head;
};
```

# 设计链表
在链表类中实现这些功能：

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

## 我的解法
```ts
// 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 head: ListNode | null;
    constructor(head?: ListNode | null) {
        this.head = head !== undefined ? head : null;
    }

    get(index: number): number {
        let nowIndex = 0;
        let now = this.head;
        while (nowIndex++ < index) {
            if (now.next === null) return -1;
            now = now.next;
        }
        console.log('now', now)
        return now?.val !== undefined ? now?.val : -1;
    }

    addAtHead(val: number): void {
        let now = new ListNode();
        now.val = val;
        now.next = this.head;
        this.head = now;
    }

    addAtTail(val: number): void {
        let insertNode = new ListNode();
        let virHead = new ListNode();
        virHead.next = this.head;
        let now = virHead;
        while (now.next !== null) {
            now = now.next;
        }
        insertNode.val = val;
        now.next = insertNode;
        this.head = virHead.next;
    }

    addAtIndex(index: number, val: number): void {
        let nowIndex = -1;
        let insertNode = new ListNode();
        let virHead = new ListNode();
        virHead.next = this.head;
        let now = virHead;
        while (nowIndex++ < index - 1) {
            if (now.next === null) return;
            now = now.next;
        }
        insertNode.next = now?.next || null;
        insertNode.val = val;
        now.next = insertNode;
        this.head = virHead.next;
    }

    deleteAtIndex(index: number): void {
        let nowIndex = -1;
        let virHead = new ListNode();
        virHead.next = this.head;
        let now = virHead;
        while (nowIndex++ < index - 1) {
            if (now.next === null) return;
            now = now.next;
        }
        now.next = now.next?.next || null;
        this.head = virHead.next;
    }
}
```

## 带size
```ts
class LinkedNode {
    public val: number;
    public next: LinkedNode;

    constructor(val: number) {
        this.val = val;
        this.next = null;
    }
}

class MyLinkedList {
    private size: number
    private head: LinkedNode;
    constructor() {
        this.size = 0;
        this.head = new LinkedNode(-1);
    }

    get(index: number): number {
        if (index < 0 || index >= this.size) {
            return -1;
        } 

        let curr = this.head;
        let i = 0;
        while (i < index + 1) {
            curr = curr.next;
            i++;
        }

        return curr.val;
    }

    addAtHead(val: number): void {
        this.addAtIndex(0, val);
    }

    addAtTail(val: number): void {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index: number, val: number): void {
        if (index < 0 || index > this.size ) {
            return;
        }
        
        let curr = this.head;
        let i = 0;
        while (i < index) {
            curr = curr.next;
            i++;
        }

        const node = new LinkedNode(val);
        node.next = curr.next;
        curr.next = node;

        this.size++;
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) {
            return;
        }

        let curr = this.head;
        let i = 0;
        while (i < index) {
            curr = curr.next;
            i++;
        }

        curr.next = curr.next.next;

        this.size--;
    }
}
```
## 带tail
```ts
// 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;
    }

    // 获取链表中第 index个节点的值
    get(index: number): number {
        // 索引无效的情况
        if (index < 0 || index >= this.size) {
            return -1;
        }
        let curNode = this.getNode(index);
        // 这里在前置条件下，理论上不会出现 null的情况
        return curNode.val;
    }

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

    // 将值为 val 的节点追加到链表的最后一个元素。
    addAtTail(val: number): void {
        let node: ListNode = new ListNode(val, null);
        if (this.tail) {
            this.tail.next = node;
        } else {
            // 还没有尾节点，说明一个节点都还没有
            this.head = node;
        }
        this.tail = node;
        this.size++;
    }

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

    // 如果索引 index有效，则删除链表中的第 index个节点。
    deleteAtIndex(index: number): void {
        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--;
    }

    // 获取指定 Node节点
    private getNode(index: number): ListNode {
        // 这里不存在没办法获取到节点的情况，都已经在前置方法做过判断
        // 创建虚拟头节点
        let curNode: ListNode = new ListNode(0, this.head);
        for (let i = 0; i <= index; i++) {
            // 理论上不会出现 null
            curNode = curNode.next!;
        }
        return curNode;
    }
}
```
# 翻转链表
## 双指针
```ts
/**
 * 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 {
    let preNode: ListNode | null = null,
        curNode: ListNode | null = head,
        tempNode: ListNode | null;
    while (curNode) {
        tempNode = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
};
```
## 递归
```ts
/**
 * 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 {
    function reserve(tail, head) {
        if (head === null) {
            return tail;
        }
        let tmp = head.next;
        head.next = tail;
        tail = head;
        return reserve(tail, tmp)
    }
    return reserve(null, head)
};
```
# 两两交换链表中的节点
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：
输入：head = []
输出：[]

示例 3：
输入：head = [1]
输出：[1]
```ts
/**
 * 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 {
    let virHead = new ListNode();
    virHead.next = head;
    let cur = virHead;
    while (cur.next && cur.next.next) {
        let temp = cur.next;
        let temp2Next = cur.next.next.next;
        cur.next = temp.next;
        temp.next.next = temp;
        temp.next = temp2Next;
        cur = cur.next.next
    }
    return virHead.next
};
```

# 删除链表的倒数第N个节点
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]
```ts
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let times = 0;
    const virHead = new ListNode();
    virHead.next = head;
    let tail = virHead;
    let del = virHead;
    while (times < n && tail?.next) {
        tail = tail.next;
        times++
    }
    if (times < n) return head;
    while (tail.next) {
        del = del.next;
        tail = tail.next;
    }
    del.next = del.next.next
    return virHead.next;
};
```
# 链表相交
![32TO.jpeg](https://img.ocer.cc/images/2024/02/21/32TO.jpeg)
```js
var getIntersectionNode = function (headA, headB) {
    let curA = headA;
    let curB = headB;
    let sizeA = 0, sizeB = 0;
    while (curA?.next) {
        curA = curA.next;
        sizeA++
    }
    while (curB?.next) {
        curB = curB.next;
        sizeB++
    }
    const diffNum = Math.abs(sizeA - sizeB);
    curA = headA;
    curB = headB;
    if (sizeA >= sizeB) {
        for (let n = 0; n < diffNum; n++) {
            curA = curA.next;
        }
    } else {
        for (let n = 0; n < diffNum; n++) {
            curB = curB.next;
        }
    }
    while (curA !== curB) {
        curA = curA?.next;
        curB = curB?.next;
    }
    return curA;
};
```
# 环形链表II
![39SV.jpeg](https://img.ocer.cc/images/2024/02/21/39SV.jpeg)
```ts
function detectCycle(head: ListNode | null): ListNode | null {
    let fast = head, slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) {
            let index1 = head;
            let index2 = fast;
            while (index1 !== index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index2
        }
    }
    return null;
};
```