# DSA - 链表

## 简介

各种数据结构的底层实现都是数组和链表，数组和链表的根本区别在于它们使用内存的方式。

如果将计算机内存简单看成下图那样，每一个内存单元就是一个小格子。

可以看到，数组是需要连续空间的，而链表则不一定。

![](https://cdn.jsdelivr.net/gh/suukii/Articles/assets/dsa_linked_list_0.png)

由于数组是连续的内存空间，因此:

* 可以按下标随机访问，访问的时间复杂度是 $O(1)$。
* 插入或者删除操作很麻烦，由于需要移动插入/删除元素后面的所有元素，时间复杂度平均是 $O(N)$。只有在数组尾部进行插入/删除操作时间复杂度才是 $O(1)$。
* 总的来说，数组是【查询友好，插入/删除不友好】。

而链表不要求连续的内存空间，各个节点可以随意散落在内存中，节点之间通过 `next` 指针连起来就行，所以：

* 需要通过遍历来查找某一个节点，访问的时间复杂度是 $O(N)$。
* 插入或者删除操作很方便，插入操作只需要在内存中随便找一个空格子存节点数据，然后把原链表尾部节点的 `next` 指针指向这个格子就好了。删除则只需要把待删除节点的空间回收，并把指向它的指针改为指向下一个节点就行。

## 基本操作

* 插入，给定节点插入位置的话，时间复杂度是 $O(1)$，否则还要遍历找到插入的节点位置，时间为 $O(N)$。
* 删除，$O(1)$，如果要先找到删除节点，时间也是 $O(N)$。
* 遍历，$O(N)$。

## 链表 vs 数组

都是线性的数据结构，只在细微的操作和使用场景上有差别。

## 考点

1. 指针的修改
2. 链表的拼接

### 指针的修改

典型的题目是 `反转链表`。

**反转链表模板**

反转任意一段链表：

JavaScript Code

```javascript
// 反转一段子链表，并返回反转后新的头尾节点
function reverse(head, tail, terminal) {
    let prev = null,
        cur = head;

    while (cur !== terminal) {
        // 保存下一个节点，防止丢失
        const next = cur.next;
        // 修改指针
        cur.next = prev;

        // 继续前移
        prev = cur;
        cur = next;
    }
    // 反转后的新的头尾节点返回出去
    return [tail, head];
}
```

### 链表的拼接

比如反转链表 II，以及合并有序链表等。

## 注意点

1. 环
2. 边界
3. 递归

## 技巧

1. 虚拟头
2. 快慢指针

## 题目

* [x] [21. 合并两个有序链表](https://github.com/suukii/91-days-algorithm/blob/master/basic/linked-list/ext-merge-two-sorted-lists.md)
* [ ] [82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
* [x] [83. 删除排序链表中的重复元素](https://github.com/suukii/91-days-algorithm/blob/master/basic/linked-list/ext-remove-duplicates-from-sorted-list.md)
* [ ] [86. 分隔链表](https://leetcode-cn.com/problems/partition-list/)
* [ ] [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
* [ ] [138. 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)
* [ ] [141. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/)
* [ ] [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
* [ ] [143. 重排链表](https://leetcode-cn.com/problems/reorder-list/)
* [ ] [148. 排序链表](https://leetcode-cn.com/problems/sort-list/)
* [x] [206. 反转链表](https://github.com/suukii/91-days-algorithm/blob/master/basic/linked-list/ext-reverse-linked-list.md)
* [ ] [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/notes/articles/dsa/dsa_linked_list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.