数据结构 - [数据结构]链表 - 《数据结构与算法》

链表, 线性数据结构。相比数组, 元素不存储在相邻位置，通指针链接。

优势：

元素个数无上限。
无需按照顺序存储。插入/删除元素，无需创建空间，无需移动插入位置以后的元素。
数组 VS 链表

数组
场景：读操作多，写操作少。优势在于快速定位元素
链表
场景：尾部频繁插入、删除元素。优势自能够灵活地进行插入和删除操作。

查找节点
更新节点
- 尾部插入
- 头部插入
- 中间插入

删除节点

尾部删除
头部删除

中间删除

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

基础

237. 删除链表中的节点

var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};

剑指 Offer 06. 从尾到头打印链表

方式1: 借助栈

var reversePrint = function(head) {
let res = [];
while (head != null) {
   res.unshift(head.val);
   head = head.next;
}
return res
};

方式2: 回溯（递归）

var reversePrint = function(head) {
if (head == null) return [];
let val = head.val;
let next = reversePrint(head.next);
return [...next, val];
};

经典

206. 反转链表

反转链表（递归）（推荐）

时间复杂度O(n) 空间复杂度O(n)

var reverseList = function(head) {
if (head == null || head.next == null) return head
var reverseedList = reverseList(head.next)
head.next.next = head
head.next = null
return reverseedList
};

反转链表（迭代）

时间复杂度O(n) 空间复杂度O(1) ```typescript 分析 cur->next->tail->prev

var reverseList = function(head) { let prev = null; let cur = head; while (cur != null) { let next = cur.next; cur.next = prev; prev = cur; cur = next; console.log(cur, prev) } return prev; };

执行过程

输入：[1,2,3,4,5] 输出：[5,4,3,2,1]

cur, prev [2,3,4,5] [1] [3,4,5] [2,1] [4,5] [3,2,1] [5] [4,3,2,1] null [5,4,3,2,1]

<a name="65612d65"></a>
#### [25. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/) [字节]

1. 划分k个一组
1. 翻转， 返回首尾
```typescript
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    let dummy = new ListNode(0, head);
    let pre = dummy;
    // pre->head-> ... ->tail-> next
    while (head != null) {
        let tail = pre;
        for (let i=0; i<k; ++i) {
            tail = tail.next;
            if (tail == null) {
                return dummy.next;
            }
        }

        let t = tail.next;
        [head, tail] = reverse(head, tail);

        // set next
        pre.next = head;
        tail.next = t;
        // set new pre and new head
        pre = tail;
        head = t;
    }
    return dummy.next;
};

function reverse (head: ListNode, tail: ListNode) {
    let cur = head;
    let pre = tail.next;
    // head -> next -> ... -> tail -> pre
    while (pre != tail) {
        let t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    return [tail, head]
}

92. 反转链表 II

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    if (head == null || head.next == null || left == right) return head;
    let dummy = new ListNode(0, head);
    let pre = dummy;
    for (let i = 0; i < left - 1; ++i) {
        pre = pre.next;
    }
    let p = pre;
    let q = pre.next;
    let cur = q;
    for (let i = 0; i < right - left + 1; ++i) {
        let t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    p.next = pre;
    q.next = cur;
    return dummy.next;
};

24. 两两交换链表中的节点

迭代（推荐）
时间复杂度 O(n)
空间复杂度 O(1)

function swapPairs(head: ListNode | null): ListNode | null {
    let dummy = new ListNode(0, head);
    let cur = dummy;
    while (cur.next != null && cur.next.next != null) {
        let p1 = cur.next, p2 = cur.next.next;
        cur.next = p2;
        p1.next = p2.next;
        p2.next = p1;
        cur = p1;
    }
    return dummy.next;
};

递归（不推荐）
时间复杂度 O(n)
空间复杂度 O(n)

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

练习1:

21. 合并两个有序链表

递归

var mergeTwoLists = function(l1, l2) {
    if (l1 == null) return l2;
    else if (l2 == null) return l1;
    else if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

迭代??

var mergeTwoLists = function(l1, l2) {
    let head = null, cur = head;
    while (l1 != null && l2 != null) {
        let node = new ListNode(l1.val <= l2.val ? l1.val : l2.val);
        if (l1.val <= l2.val) {
            l1 = l1.next;
        } else {
            l2 = l2.next;
        }
        if (head == null) {
            head = node
            cur = head;
        } else {
            cur.next = node;
            cur = cur.next;
        }
    }
    if (l1 != null) {
        cur.next = l1;
    }
    if (l2 != null) {
        cur.next = l2;
    }
    return head;
};

234. 回文链表

var isPalindrome = function(head) {
    if (head == null) return true;
    let p1 = head;
    let halfHead = findMid(head);
    let p2 = reverseList(halfHead.next); // 注意
    while (p2 != null) {
        if (p1.val != p2.val) return false;
        p1 = p1.next;
        p2 = p2.next;
    }
    return true;
};

function findMid (head) {
    let fast = head;
    let slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

// 辅助函数
function reverseList (head) {
    if (head == null || head.next == null) return head;
    let reversedHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reversedHead;
}

借助dummy

203. 移除链表元素

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

2. 两数相加

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode();
    let carry = 0, cur = dummy;
    while (l1 != null || l2 != null || carry != 0) {
        let num1 = l1 == null ? 0 : l1.val;
        let num2 = l2 == null ? 0 : l2.val;
        let sum = num1 + num2 + carry;
        carry = parseInt(sum / 10);
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
};

147. 对链表进行插入排序

当前值 > 前一个值
1. 是，继续
2. 从头遍历，放在合适位置

参考：
https://leetcode-cn.com/leetbook/read/linked-list/jqjdj/
https://www.geeksforgeeks.org/data-structures/linked-list/
https://www.geeksforgeeks.org/linked-list-in-java/

[数据结构]链表

数组 VS 链表

数组

链表

基础

经典

反转链表（递归）（推荐）

反转链表（迭代）

练习1:

借助dummy