Published on

链表

Authors

链表

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

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

链表「换头」情况

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

哨兵守卫

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

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

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

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

/**
 * 奇数的中点; 偶数的中点靠前一位
 */
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版本:这道题要是空间复杂度不需要 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
}
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;
    }
}

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

进阶:有环单链表相交
/**
 * 有环单链表相交要分清楚情况:
 * 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

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

// 迭代法,那就是双指针了,先存储后继节点,剩下的都好办
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
}

插入一下Java哈希表的了解

在 javascript 中的 Set 和 Map 咱就不说啥了,非正规军 😄。来看看 java 的:

  1. 无序表
    • HashSet: add remove contains,对呀 c++ 中的 unordered_set
    • HashMap: put remove containsKey,对应 c++ 中的 unordered_map
  2. 有序表
    • TreeSet:它是按升序对元素进行排序,对应 c++ 中的 ordered_set
    • TreeMap:基于红黑树的 NavigableMap 实现,它根据其键的自然顺序排序,对应 c++ 中的 ordered_map

记得之前学 java 的时候, HashSet 底层就是 HashMap,只不过没有 value 只有 key 罢了,而常规的 HashMap 的底层则是 链表,在 java 中,当链表的长度到达 8 时,就会自动扩容,链表也会重新分配,好像有红黑树什么的(不清楚,后序学习再回头补充),后面了解到哈希函数的时候,就更加清楚了,离散函数使得分配空间时基本是离散均匀的。

  1. 放入无/有序表的东西,如果是基础类型,内部按值传递,内存占用就是这个东西的大小
  2. 放入无序表的东西,如果不是基础类型,内部按引用传递,内存占用的就是这个东西的内存地址的大小,java 中是 8 个字节
  3. 放入有序表的东西,如果不是基础类型,必须提供比较器,内部按引用传递...。

重点:无序表 的增删改查的时间复杂度都是 常数 级别(比较大的常数 哈哈),有序表的时间复杂度都是 O(logn) 级别