# 链表

链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来使用。常见的链表结构:单链表、双向链表、循环链表

相对于数组,插入、删除效率更高O(1),随机访问效率更低O(n),内存空间消耗更大。

对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片。

# 回文字符串(Topic:206)

# 思路

快指针走两步,慢指针走一步。快指针到达终点时,慢指针刚好到好中间点。复制一个慢指针,分别往回走和往终点走,依次比较是否相同。(注意快指针超出长度的情况)

# 代码实现

// 时间复杂度O(n),空间复杂度O(1)
function palindromicString(str) {
    let fast = slow = 0
    // 要减去1,因为从0开始的
    const len = str.length - 1
    while(fast < len) {
        fast += 2
        slow++
    }
    let cur = slow
    // 长度为偶数时,多走过了一步
    if (fast > len) {
        fast = len  // 此句可忽略,因为fast后面用不到了
        slow--
    }
    
    while(slow >= 0) {
        if (str[slow] !== str[cur]) {
            return false
        }
        cur++
        slow--
    }
    return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 简单反转

# 思路

从头节点开始依次往下修改next的结点,next结点为上一个结点,那么头结点的next结点为null。(注意:要将下一个结点进行保存,否则会造成丢失。)

# 代码实现

  • 解法一:
class Node {
    constructor(val) {
        this.val = val
        this.next = null
    }
}

let reverseList = (head) => {
    if (!head) return null
    let pre = null, cur = head
    while(cur) {
        const next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 解法二:递归
let reverseList = (head) => {
    let reverse = (pre, cur) => {
        if (!cur) return pre
        const next = cur.next
        cur.next = pre
        return reverse(cur, next)
    }
    reverse(null, head)
}
1
2
3
4
5
6
7
8
9

# 区间反转(Topic:92)

# 思路

找到第m-1个结点,反转m-n之间的结点(此时mnext应该为第n+1个结点,但是暂时不知道,所以只能先反转m+1n区间的结点),纠正需要修改的next

# 代码实现

// 1 ≤ m ≤ n ≤ 链表长度。
const reverseBetween = (head, m, n) => {
    // 为什么还要用一个变量来存储,因为后面的for循环改变了p的地址
    let p = dummyHead = new ListNode()
    p.next = head

    // 找到m前一个结点
    for(let i = 1; i < m; i++) {
        p = p.next
    }
    
    // 保存m前一个结点
    let front = p
    // 保存第m个结点
    let pre = tail = p.next
    // 从第m+1个结点开始反转
    let cur = pre.next
    for(let i = m + 1; i <= n; i++) {
        const next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    // for循环之后,cur为第n+1个结点,pre为原第n个结点

    // m前一个结点指向原第n个结点
    front.next = pre
    // 原第m个结点指向第n+1个结点
    tail.next = cur
    return dummyHead.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
25
26
27
28
29
30
31

# 两两一组翻转(Topic:Lc24 (opens new window)

# 思路

建立一个虚拟头结点,判断下一组结点是否存在,交换之后要修改next指向,否则会丢失结点

# 代码实现

  • 解法一:
var swapPairs = function(head) {
    let p = dummyHead = new ListNode()
    p.next = head
    while((n1 = p.next) && (n2 = p.next.next)) {
        n1.next = n2.next
        n2.next = n1

        // 两两交换之后,改变上一个结点的next
        p.next = n2

        p = n1
    }
    return dummyHead.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 解法二(递归):
var swapPairs = function(head) {
    if (head === null || head.next === null) return head
    let n1 = head, n2 = head.next
    n1.next = swapPairs(n2.next)
    n2.next = n1
    return n2
};
1
2
3
4
5
6
7

# K个一组翻转(Topic:Lc25 (opens new window)

# 思路

# 代码实现

  • 解法一:

  • 解法二(递归):

var reverseKGroup = function(head, k) {
    let p = head, cur = head, pre = null
    // 一组
    for (let i = 1; i <= k; i++) {
        if (p === null) return head
        p = p.next
    }

    // 翻转
    for (let i = 1; i <= k; i++) {
        const next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    head.next = reverseKGroup(cur, k)
    return pre
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 中环检测(Topic:Lc141 (opens new window)

# 有序链表合并(Topic:Lc21 (opens new window)

# 删除链表倒数第n个结点(Topic:Lc19 (opens new window)

# 链表中间结点(Topic:Lc876 (opens new window)