基本技巧

Basic Linked List Skills

1. 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)
     

• 递归遍历

  • 先序遍历

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

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

  • 后序遍历

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

    可以用于：

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

2. Insert a Node in Sorted List

   如：将node插入到p的后面

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

3. Remove a Node from Linked List

4. Reverse a Linked List

   见同向双指针内

5. Merge Two Linked Lists

   见平行双指针内，这个是

6. Middle of a Linked List