链表 | BaoTao的前端日志

链表

数组的优势，在查询数组指定位置（如查询数组中的第4个数据）的操作中，只需要进行1次操作即可，时间复杂度为O(1)。但是，这种时间上的便利性，是因为数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，本质是指针在内存中的定向偏移。然而，当需要对数组成员进行添加和删除的操作时，数组内完成这类操作的时间复杂度则变成了O(n)。

链表的特性，使其在某些操作上比数组更加高效。例如当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。另外，因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。

基本的链表构造函数

function ListNode(x){
    this.val = x;
    this.next = null;
}

1
2
3
4

模拟链表数据结构：

var node5 = { val: 5, next: null };
var node4 = { val: 4, next: node5 };
var node3 = { val: 3, next: node4 };
var node2 = { val: 2, next: node3 };
var node1 = { val: 1, next: node2 };
实际结构如下: 1->2->3->4->5->NULL

1
2
3
4
5
6

剑指Offer

链表反转打印和链表反转：可以采用栈实现链表的反转打印，也可以采用三个指针实现链表的反转然后实现链表的打印。

function ReverseList(pHead)
{
    if (pHead == null) {
        return false;
    }
    var head = new ListNode(0)
    // head永远指向第一个节点
    head.next = pHead
    var prev = pHead
    var pCur = pHead.next
    while(pCur) {
        // 假设链表为 1 -> 2 -> 3, 第一次循环需要变为2 -> 1 -> 3
        // head.next指向1，prev.next指向2，pCur.next指向3
        // 第一步是让1 -> 3,如果是2 -> 1则无法再找到3
        prev.next = pCur.next
        // 然后是2 -> 1，因为head永远指向第一个节点，所以需要用head.next,不是prev
        pCur.next = head.next
        // 修正head的指向
        head.next = pCur
        pCur = prev.next
    }
    return head.next
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

打印倒数第K个节点：设置两个指针p1，p2，先让p2走k-1步，然后再一起走，直到p2为最后一个时，p1即为倒数第k个节点。

链表相加：注意逻辑即可，没有难度。

链表的复制：通过递归实现

function Clone(pHead) {
    if (!pHead) {
        return null;
    }
    var newHead = new RandomListNode(pHead.label);
    newHead.random = pHead.random;
    newHead.next = Clone(pHead.next);
    return newHead;
}

1
2
3
4
5
6
7
8
9

二叉搜索树转为双向链表：利用中序遍历，然后更改每个节点的指针指向即可。

找出链表的公共节点：先找出两个链表的长度，然后长的先走n-m,最后到两个指针相同时即为公共节点

更简单的方法采用两个指针遍历链表，若为空则指向另一个链表的头，最终两个指针相等即可。

删除链表中重复的节点：遍历链表，用两个指针，若存在重复节点则一个指针会一直移动到重复节点末尾，判断两个节点是否相等再进行相关操作。

function deleteDuplication(pHead) {
    if(pHead == null || pHead.next == null){
        return pHead; //只有0个或1个结点，则返回
    }
    var newHead = new ListNode(0);
    newHead.next = pHead;
    var prev = pHead, current = newHead;
    // prev为null，表示遍历完成
    while(prev) {
        // 循环找到重复节点的最后一个
        while(prev.next !== null && prev.next.val === prev.val ) {
            prev = prev.next;
        }
        // 若不相等，则有重复节点，进行跳过
        if(current.next !== prev) {
            prev = prev.next;
            current.next = prev;
        } else {
            current = current.next;
            prev = prev.next;
        }
    }
    return newHead.next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

判断链表环的入口节点：设定两个快慢节点，当有环时快慢节点相遇（快指针速度为2，慢指针速度为1），我们可以知道2(x+y) = (x+y+z+y),x为环之外的长度，而y是相遇时距入口节点的距离，z+y为环总共的长度。得到了y = z,然后新增两个指针，一个指针从头结点开始遍历，一个指针从相遇处开始遍历，两指针相等处则为环入口。

function EntryNodeOfLoop(pHead) {
    if(pHead === null) {
        return 1
    }
    if(pHead.next === null) {
        return null
    }
    var fast = pHead;
    var slow = pHead;
    while(slow != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if(fast === slow) break;
    }
    var p1 = slow;
    var p2 = pHead;
    while(p1 !== p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

← 二叉树 CSS的repaint和reflow →

# 链表

# 剑指Offer

链表

剑指Offer