链表

EricYuan 收录于类别 Algorithm 和系列 Data Structure 阅读量次

2024-01-09 2024-03-04 约 2517 字预计阅读 12 分钟

系列 -

链表

java

class Node<V> {
  V value;
  Node next;
}
class Node<V> {
  V value;
  Node next;
  Node last;
}

对于链表算法，在面试中，一定尽量用到空间复杂度最小的方法（不然凭啥用咱是吧 🐶）。

链表「换头」情况

操作链表出现「换头」的情况，函数的递归调用形式应该是 head = func(head.next)，所以函数在设计的时候就应该有一个 Node 类型的返回值，比如反转链表。

哨兵守卫

「哨兵守卫」是链表中的常用技巧。通过在链表头部或尾部添加守卫节点，可以简化对边界情况的处理。

链表中常用的技巧-快慢指针

找到链表的中点、中点前一个、中点后一个

这个是硬编码能力，需要大量练习打好基本功。

java

/**
 * 奇数的中点; 偶数的中点靠前一位
 */
Node s = head;
Node f = head;
while (f.next != null && f.next.next != null) {
    s = s.next;
    f = f.next.next;
}

/**
 * 奇数的中点; 偶数的中点靠后一位 lc.876 easy
 */
while (f != null && f.next != null) {
    s = s.next;
    f = f.next.next;
}

如果要进一步继续偏移，修改 f 或 s 的初始节点即可。

注意：因为 f 一次走两步，所以：

想要获取中点往前的节点，修改 f 初始节点时 f=head.next.next，两个 next 才会让结果往前偏移一步
想要获取中点往后的节点，修改 s 的初始节点 s=head.next，一个 next 就可以让结果往后偏移一步

练习

lc.2 两数相加

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    let dummy = new ListNode(-1)
    let p = dummy

    let p1 = l1,
        p2 = l2
    let carry = 0
    while (p1 || p2) {
        let a = p1 ? p1.val : 0
        let b = p2 ? p2.val : 0
        let sum = a + b + carry
        carry = (sum / 10) | 0
        p.next = new ListNode(sum % 10)
        p = p.next
        p1 = p1 ? p1.next : null
        p2 = p2 ? p2.next : null
    }
    if (carry) {
        p.next = new ListNode(carry)
    }
    return dummy.next
}

lc.19 删除链表倒数第 N 个节点

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    let p = head
    while (n--) {
        p = p.next
    }
    let dummy = new ListNode(-1, head)
    let p2 = dummy
    while (p) {
        p = p.next
        p2 = p2.next
    }
    p2.next = p2.next.next
    return dummy.next
}

lc.2 和 lc.19 是 dummy 守卫节点的最佳实践了，一个是新增，一个是删除。

lc.21 合并两个有序链表 easy

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    let dummy = new ListNode(-1)
    let p = dummy
    let p1 = list1,
        p2 = list2
    while (p1 && p2) {
        if (p1.val < p2.val) {
            p.next = p1
            p1 = p1.next
        } else {
            p.next = p2
            p2 = p2.next
        }
        p = p.next
    }
    if (p1) p.next = p1
    if (p2) p.next = p2
    return dummy.next
}

lc.23 合并 K 个有序链表 hard

这道题比较朴素的做法是：已知两个有序链表的合并，那么遍历所有链表逐条合并即可。

性能强一点的做法是利用优先队列。JS 中没有，得先手动实现；Java 中有 PQ，得设置比较函数。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    let dummy = new ListNode(-1)
    let p = dummy
    lists = lists.filter(item => item !== null)
    const pq = new PQ(lists, (a, b) => a > b)
    while (!pq.isEmpty()) {
        const top = pq.pop()
        p.next = top
        p = p.next

        if (top && top.next) {
            pq.push(top.next)
        }
    }
    return dummy.next
}

/** 手动实现优先队列 */
class PQ {
    constructor(data, comparator) {
        this.data = data
        this.comparator = comparator
        for (let i = data.length >> 1; i >= 0; --i) this.down(i)
    }
    up(i) {
        while (i > 0 && this.comparator(this.data[(i - 1) >> 1].val, this.data[i].val)) {
            this.swap((i - 1) >> 1, i)
            i = (i - 1) >> 1
        }
    }
    down(i) {
        let left = 2 * i + 1
        while (left < this.data.length) {
            let min = left
            if (left + 1 < this.data.length) {
                min = this.comparator(this.data[left + 1].val, this.data[left].val)
                    ? left
                    : left + 1
            }
            min = this.comparator(this.data[i].val, this.data[min].val) ? i : min
            if (min === i) break
            this.swap(min, i)
            i = min
            left = 2 * i + 1
        }
    }
    push(val) {
        this.up(this.data.push(val) - 1)
    }
    pop() {
        this.swap(0, this.data.length - 1)
        const top = this.data.pop()
        this.down(0)
        return top
    }
    swap(i, j) {
        const temp = this.data[i]
        this.data[i] = this.data[j]
        this.data[j] = temp
    }
    isEmpty() {
        return this.data.length === 0
    }
}

另一种递归解：归并

var mergeKLists = function (lists) {
    if (lists.length === 0) return null
    if (lists.length === 1) return lists[0]
    const mid = lists.length >> 1
    const left = mergeKLists(lists.slice(0, mid))
    const right = mergeKLists(lists.slice(mid))
    return mergeTwoList(left, right)
}
function mergeTwoList(a, b) {
    if (!a) return b
    if (!b) return a
    if (a.val < b.val) {
        a.next = mergeTwoList(a.next, b)
        return a
    } else {
        b.next = mergeTwoList(a, b.next)
        return b
    }
}

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

不错的一道题

var swapPairs = function (head) {
    if (head === null || head.next === null) return head
    const newHead = head.next // cache
    head.next = swapPairs(head.next.next)
    newHead.next = head // 归 - 后序位置
    return newHead
}

/** 迭代解法 */
var swapPairs = function (head) {
    const dummy = new ListNode(-1)
    dummy.next = head
    let p = dummy
    while (p.next !== null && p.next.next !== null) {
        const a = p.next // cache
        const b = p.next.next // cache

        p.next = b
        a.next = b.next
        b.next = a
        p = a
    }
    return dummy.next
}

可以看见，无论是递归还是迭代，因为要变动后方的节点，所以一般都可以先做一层缓存。

lc.83 删除链表的重复元素 easy

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let p = head
    while (p && p.next) {
        if (p.val === p.next.val) {
            p.next = p.next.next
        } else {
            p = p.next
        }
    }
    return head
}

单链表分区（左<,中=,右>）

在三路快排中，有类似的操作。所以如果借助数组，那么就是荷兰国旗问题了。

但是这样做时间复杂度就高了，对于链表，能用指针操作的，就不借助额外空间。要想空间复杂度为 O(1)，那么就得借助 6 个变量 <head <tail， =head =tail， >head >tail。

lc.86 分隔链表

这道题是上方分区的简化版本，只用把小于 X 的节点放到大于等于 X 的节点之前即可。

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
    if (head === null || head.next === null) return head
    let small = new ListNode(-1)
    let large = new ListNode(-1)
    let p = head,
        p1 = small,
        p2 = large
    while (p !== null) {
        const val = p.val
        if (val < x) {
            p1.next = p
            p1 = p1.next
        } else {
            p2.next = p
            p2 = p2.next
        }

        p = p.next
    }
    p2.next = null // 注意需要给大的收尾~
    p1.next = large.next
    return small.next
}

lc.138 复制含有随机指针的链表

java

/**
 * Java版本：这道题要是空间复杂度不需要 O(1)，那么用哈希表就挺好做的
 *
 * O(1) 的空间复杂度，就需要一定的技巧了，就是 拼接+拆分。
 */
 // 哈希表
class Solution {
  public Node copyRandomList(Node head) {
      Map<Node, Node> map = new HashMap<>();
      Node p = head;
      while (p != null) {
          map.put(p, new Node(p.val));
          p = p.next;
      }
      p = head;
      while(p != null) {
          map.get(p).next = map.get(p.next);
          map.get(p).random = map.get(p.random);
          p = p.next;
      }
      return map.get(head);
  }
}
/** 空间复杂度 O(1) */
public Node copyRandomList(Node head) {
  // 恰到好处的拼接，复制节点直接拼到原节点后，这样会发现：
  // ** 新节点的random指向的就是原节点random指向节点的下一个节点 **
  // 1.复制节点
  Node p = head;
  while (p != null) {
      Node newNode = new Node(p.val);
      newNode.next = p.next;
      p.next = newNode;
      p = newNode.next;
  }
  // 2.设置 random
  p = head;
  while (p != null) {
      if(p.random != null) {
          p.next.random = p.random.next;
      }
      p = p.next.next;
  }
  // 3. 分离链表
  Node dummy = new Node(-1);
  p = head;
  Node curr = dummy;
  while (p != null) {
      curr.next = p.next;
      curr = curr.next;
      p.next = curr.next;
      p = p.next;
  }
  return dummy.next;
}

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
    /** 尽可能降低空间复杂度，使用拼接技巧 */
    let p = head
    while (p !== null) {
        const cpNode = new Node(p.val)
        cpNode.next = p.next
        p.next = cpNode
        p = cpNode.next
    }
    p = head
    while (p !== null) {
        if (p.random) {
            p.next.random = p.random.next
        }
        p = p.next.next
    }
    const dummy = new Node(-1)
    let curr = dummy
    p = head
    while (p !== null) {
        curr.next = p.next
        curr = curr.next
        p.next = curr.next
        p = p.next
    }
    return dummy.next
}

单链表环相关问题

快慢指针判断是否有环的原理是：如果有环，则必定两个指针会相遇；否则，快指针将走到空。

lc.141 判断链表是否有环 easy

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    if (head == null) return false
    let f = head.next,
        s = head
    while (true) {
        if (f == null || f.next == null) return false
        s = s.next
        f = f.next.next
        if (s === f) return true
    }
    // 下面那种写法也行
    // if (head == null) return false
    // let s = head,
    //     f = head.next // !!! 注意这里是先走了一步的
    // while (s !== f) {
    //     if (f == null || f.next == null) return false
    //     s = s.next
    //     f = f.next.next
    // }
    // return true
}

lc.142 返回环的起点

此题应用的是著名的 Floyd 判圈算法（维基百科）。应用快慢指针，第一次相遇后快指针回到头部和慢指针一起走，再次相遇就是环的起点。

假设 head 到环起点的距离为 a，环起点到快慢指针相遇的距离为 b，环长度为 c ，则：

慢指针走了 a + b，
快指针走了 a + b + n*c， n 为圈数

第一次相遇时，慢指针走 k，快指针走 2k，快比慢多走了 k 步，所以 n * c = k，因此 k 是环的整数倍。所以回到起点的指针要再走 k - b 步才到起点，而从第一次相遇点走到环起点的距离也恰好也为 k - b。

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
    if (head === null || head.next === null) return null
    let s = head,
        f = head
    while (true) {
        if (f == null || f.next == null) return null
        s = s.next
        f = f.next.next
        if (s === f) break
    }

    f = head
    while (s !== f) {
        f = f.next
        s = s.next
    }
    return s
}

单链表相交问题

处理链表相交一类的问题，核心在于 「抹除长度差异」，然后齐头并进，有相等节点则相交。

lc.160 相交链表 easy

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    if (headA == null || headB == null) return null

    let n = 0
    let p1 = headA,
        p2 = headB // 假定 p1 为长，p2 为 短
    while (p1 !== null) {
        n++
        p1 = p1.next
    }
    while (p2 !== null) {
        n--
        p2 = p2.next
    }

    if (n > 0) {
        p1 = headA
        p2 = headB
    } else {
        p1 = headB
        p2 = headA
    }

    n = Math.abs(n)
    while (n--) {
        p1 = p1.next
    }

    while (p1 !== p2) {
        p1 = p1.next
        p2 = p2.next
    }

    return p1
}

java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode l = headA, s = headB;
        int n = 0;
        while (l != null) {
            n++;
            l = l.next;
        }
        while (s != null) {
            n--;
            s = s.next;
        }
        if (l != s) return null;
        l = n > 0 ? headA : headB;
        s = n > 0 ? headB : headA;
        n = Math.abs(n);
        while (n != 0) {
            l = l.next;
            n--;
        }
        while (l != s) {
            l = l.next;
            s = s.next;
        }
        return l;
    }
}

有个取巧的小技巧是，当两个指针第一次走到末尾后，分别跳到对方链表上去，这样等价于抹除了长度差异，如有相交，则会走到相同节点上。具体见官解。

进阶：有环单链表相交

java

/**
 * 有环单链表相交要分清楚情况：
 * 1. 不相交
 * 2. 环的起始节点一样，则把这个起始节点看成两个无环链表的终点，利用上题的解法求出相交节点即可
 * 3. 环的起始节点不一样，则这两个节点都是相交节点，返回任意一个即可
 *
 * 1 和 3 情况的区分是，一个环的节点继续走，走回自己之前能遇到另一个环的节点就是情况3，否则就是情况1
 */
public ListNode bothLoop(ListNode head1, ListNode head2, ListNode loop1, ListNode loop2) {
    /**
     * 第 2 种情况，两个有环链表共用环起点，
     * 那么此时可以把环的起点看成是head1和head2到的无环链表的终点，
     * 也就转化成了寻找两个无环单链表相交点的问题了。
     */
    if (loop1 == loop2) {
        ListNode p1 = head1, p2 = head2;
        int n = 0;
        while (p1 != loop1) {
            n++;
            p1 = p1.next;
        }
        while (p2 != loop2) {
            n--;
            p2 = p2.next;
        }
        p1 = n > 0 ? head1 : head2;
        p2 = n > 0 ? head2 : head1;
        n = Math.abs(n);
        while (n > 0) {
            p1 = p1.next;
            n--;
        }
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    } else {
        /**
         * 第 1 种情况不相交和第 3 种情况相交在环上不同的节点
         * 区分方式是让节点从 loop1 开始继续绕环走，能遇到 loop2 则说明相交了，否则为不相交
         */
        ListNode p = loop1.next; // 先前进一步，否则while进不去喽～
        while (p != loop1) {
            if (p == loop2) {
                return loop2; // loop1 loop2都是相交点，随意返回一个
            }
            p = p.next;
        }
        return null;
    }
}

反转链表问题

lc.206 反转链表 hot easy

最基本的考验对双指针和递归的理解。不错的一道经典题。

java

// 迭代法，那就是双指针了，先存储后继节点，剩下的都好办
public ListNode reverseList(ListNode head) {
    ListNode p = head, pre = null;
    while(p != null) {
        ListNode next = p.next; // 储存后继节点
        p.next = pre;
        pre = p;
        p = next;
    }
    return  pre;
}
// 递归法
public ListNode reverseList(ListNode head) {
  if (head == null || head.next == null) return head;
  ListNode newHead = reverseList(head.next); // newHead 是最后一个节点
  // 后序遍历，假设递归到最后了，此时的 head 是最后一个节点的前一个节点
  head.next.next = head; // 把下一个节点的next指向自身
  head.next = null; // 把自身的next指向null
  return newHead; // 返回尾部节点的引用指针即可
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    if (!head || !head.next) return head
    const newHead = reverseList(head.next)
    head.next.next = head
    head.next = null
    return newHead
}

var reverseList = function (head) {
    let p = head,
        pre = null
    while (p) {
        const next = p.next
        p.next = pre
        pre = p
        p = next
    }
    return pre
}

lc.92 反转链表 II

如果不要求只一次遍历，利用 lc.206 就可以完成了。

只能遍历一次的话，需要技巧，就是每遍历到反转区间内的一个元素，就把这个元素放到反转区间的头部。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
    const dummy = new ListNode(-1) // left 可能为头，守卫简化操作
    dummy.next = head

    let p = dummy
    for (let i = 0; i < left - 1; ++i) {
        p = p.next
    }
    // 此时，p 指向区间的前一个节点

    const len = right - left + 1
    let curr = p.next
    let step = len - 1
    while (step--) {
        const next = curr.next
        curr.next = next.next
        next.next = p.next
        p.next = next
    }

    return dummy.next
}

lc.25 K 个一组反转链表 hard

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    if (head === null) return head
    let a = (b = head)
    for (let i = 0; i < k; ++i) {
        if (b == null) return head // 不足 k
        b = b.next
    }

    const newHead = reverse(a, b)
    a.next = reverseKGroup(b, k) // [a, b) 反转后 a 的 next 为剩下的链表反转
    return newHead
}

/**
 * 反转 [head, tail) 区间的链表，其实普通的反转链表反转的就是 [head, null) 区间罢了
 */
function reverse(head, tail) {
    let prev = null,
        curr = head
    while (curr !== tail) {
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

lc.234 回文链表 easy

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
    if (head === null) return false
    let s = head,
        f = head
    while (f !== null && f.next !== null) {
        s = s.next
        f = f.next.next
    }

    // 对后半部分， s 进行反转
    let prev = null
    while (s !== null) {
        const next = s.next
        s.next = prev
        prev = s
        s = next
    }

    // 对 prev 和 head 进行比较
    while (prev) {
        if (prev.val !== head.val) return false
        prev = prev.next
        head = head.next
    }

    return true
}

目录

链表

链表

链表「换头」情况

哨兵守卫

链表中常用的技巧-快慢指针

找到链表的中点、中点前一个、中点后一个

练习

lc.2 两数相加

lc.19 删除链表倒数第 N 个节点

lc.21 合并两个有序链表 easy

lc.23 合并 K 个有序链表 hard

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

lc.83 删除链表的重复元素 easy

单链表分区（左<,中=,右>）

lc.86 分隔链表

lc.138 复制含有随机指针的链表

单链表环相关问题

lc.141 判断链表是否有环 easy

lc.142 返回环的起点

单链表相交问题

lc.160 相交链表 easy

进阶：有环单链表相交

反转链表问题

lc.206 反转链表 hot easy

lc.92 反转链表 II

lc.25 K 个一组反转链表 hard

lc.234 回文链表 easy