链表

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

相对于数组，插入、删除效率更高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
}

简单反转

思路

从头节点开始依次往下修改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
}

• 解法二：递归

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)
}

区间反转（Topic：92）

思路

找到第m-1个结点，反转m-n之间的结点（此时m的next应该为第n+1个结点，但是暂时不知道，所以只能先反转m+1至n区间的结点），纠正需要修改的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
}

两两一组翻转（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
};

• 解法二（递归）：

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
};

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
};

中环检测（Topic：Lc141 (opens new window)）

有序链表合并（Topic：Lc21 (opens new window)）

删除链表倒数第n个结点（Topic：Lc19 (opens new window)）

链表中间结点（Topic：Lc876 (opens new window)）