Fl0w3r

carpe diem

Linked List

Posted on In
2k 4 mins.

引言

Linked List 是比较常见的数据结构，以下我们会介绍 Linked List 题目中常用的双指针（Two Pointers）和递归（Recursion）方法，可以用于解决一系列常见的题目。

Linked List vs. Array

Array 一组内存里连续的数据

  • 能用 index 访问 –> $O(1)$ Access
  • 添加元素直接添加在最后 –> Amortized $O(1)$ Add（考虑到扩容）
  • 删除元素需要挪动后面所有元素位置 –> $O(n)$ Delete

Linked List 内存里不一定连续的数据

  • 不能用 index 访问 –> $O(n)$ Access
  • 添加元素添加在最后 –> $O(n)$ Add 双链表 $O(1)$
  • 删除元素需要找到元素位置 –> $O(n)$ Delete
class ListNode {
  int val;
  ListNode next;
}

Two Pointers

  • 两个指针指向 Linked List 节点，不再是 index
  • 两个指针必定同向而行

Two Pointers 方法大概能解决 60% 的 Linked List 问题，对于每道题只需要记住定义这两点：

  1. 一个快一个慢，距离隔开多少
  2. 两个指针移动速度

Linked List 找中间节点

两个指针同向而行，一个每次前进 2 个节点，另一个每次前进 1 个节点，当快的指针到最后，慢的指针就停留在了中点。

对于第一个偶数链表来说中间节点是 2 或 3 都可以，对于第二个奇数链表中间节点就是最中间的 3。

High Level Idea:

  1. Initialize 2 pointers i and j pointing to the head
  2. While the next move of the faster pointer j is valid (inside bound), move j two steps and i one step forward
  3. Return the node at i
ListNode linkedlistMiddleNode(ListNode head) {
  ListNode i = head, j = head;
  while(j != null && j.next != null) {
    i = i.next;
    j = j.next.next;
  }
  return i;
}

Linked List 找倒数第k个节点

两个指针先隔开 k 个位置，然后每次相同速度向前直到快指针出界，慢指针就停留在倒数第 k 个节点。

High Level Idea:

  1. Initialize 2 pointers i and j pointing to the head
  2. Move j k step forward
  3. Move both i and j one step forward at a time until j is out of bound
ListNode linkedlistLastKNode(ListNode head, int k) {
    ListNode i = head, j = head;

    for (int n = 0; n < k; ++n) 
        j = j.next;
    
    while (j != null && j.next = null) {
        i = i.next;
        j = j.next;
    }
    return i;
}

Recursion

面试时可能会刻意考察 recursion 是否理解，尤其是简单的题目。

Bottom up recursion 3 steps:

  1. Asek for subproblem result
  2. Do something in current level of recursion
  3. Return result

Recursion 最重要的一点：相信自己的 recursion function 是对的。

Reverse Linked List

这里举个简单的例子，倒置链表。注意倒置不仅仅是数值的变化，还有指针引用的改变。

我们假设 3 后面已经 Reversed 好了，不会管他里面什么样，相当于一个黑盒不需要知道里面的内容。对于 3 这一层来说首先要把 3.next 的指针返回到 3：

3.next.next = 3;

然后需要把 3 的 next 指针收回：

3.next = null;

对于每一层的 recursion:

  1. 问下一次要结果
  2. Reverse 当前所在的 ListNode
  3. 返回 reversed head

High Level Idea:

  1. Ask for next recursion level result
  2. Reverse current node
  3. Return reversed head
ListNode reverse(ListNode head) {
  if(head == null || head.next = null)
    return head;
  
  ListNode reverse_head = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return reverse_head;
}

总结

大家可以通过更多类似题目进行练习：

  1. Delete Node In a Linked List (237)
  2. Linked List Cycle (141)
  3. Reverse Linked List II (92)
  4. Reverse Nodes In k-Group (25)
Related Posts