基本技巧

Basic Linked List Skills

Traversal

Iterative traversal

// FOR：先序：访问
ListNode p = head;
while (p != null) {
    // TODO
    
    p = p.next;
}

// FOR：先序：访问
ListNode p = dummy;
while (p.next != null) {
    // TODO
    
    p = p.next;
}

// 写法2，单指针，局部变量，且移动语句受限
for (ListNode p = head; p != null; p = p.next) {
    // TODO
}

Recursive traversal

• 先序遍历

  优点：可以用递归三要素分析，边界条件可以定义的很清晰

  很少用，先序遍历都可以直接写做迭代，使用递归会徒增递归的空间复杂度为On

• 后序遍历

  优点：可以“反着”遍历单链表，“获得”前驱节点

  可以用于：

  • 反转链表，这个情况写起来非常简洁，但是空间复杂度On
  • 回文链表

Manipulation

1. Insert a Node in Sorted List

   如：将node插入到p的后面

   node.next = p.next;
   p.next = node;

2. Remove a Node from Linked List

   1. Prev

      node.next = node.next.next;

   2. 李代桃僵法（不适用于尾节点）

      node.val = node.next.val;
      node.next = node.next.next;

3. Reverse a Linked List

   见同向双指针内

4. Merge Two Linked Lists

   见平行双指针内

5. Middle of a Linked List

   见快慢双指针

6. Cycle Detection

   见快慢双指针

3217. Delete Nodes From Linked List Present in Array

You are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes from the linked list that have a value that exists in nums.

ListNode modifiedList(int[] nums, ListNode head) {
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) {
        numSet.add(num);
    }

    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    while (prev != null && prev.next != null) {
        ListNode curr = prev.next;
        if (numSet.contains(curr.val)) {
            prev.next = prev.next.next;
        } else {
            prev = prev.next;
        }
    }

    return dummy.next;
}