LinkedList

Dummy Node

• 什么时候使用 Dummy Node?
  • 当头结点会变化，例如有两个heads的时候
• 如何使用 Dummy Node?
  • ListNode dummy = new ListNoe(0)
  • ListNode lastNode = dummy
  • 最后return dummy.next

• head = dummy 这句话总是需要么? No

• Dummy Node 是否需要删除? No，但是记得要考虑新的LL最后要指向NULL

• 使用 Dummy Node 算面试官会说我耗费了额外空间么?
• Dummy Node 非用不可么?

Basic Operation

Delete

• 一般情况下cur.next = cur.next.next
• 在无法获得preNode的情况下，可以通过把nextNode转移(只是转移val)到当前node，来删除当前node e.g

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

Swap

temp = a;
a = b;
b = temp;

swap two nodes in LL

• 遇到这类交换的题目，标记清楚preNode, postNode即可

Reverse - 这里的reverse以后原LL发生了变化

把第一个节点指向空节点

• 创建空节点pre
• 保留第一个节点的next
• 将第一个节点指向pre, 理解每一次变换，就是将head节点的next指针由原来的head.next改为指向head.pre
• 对于Reverse LL，第一次就是将head.next改为指向pre (null)
• 对于Reverse LL II，第一次就是对需要reverse的那一部分的第二个点的next进行操作

经过这个变换以后，pre指向reversed LL的第一个node

• 注意，如果变换的是LL的一部分，那么原先的头结点指向null，尾节点为变换后的起点

public ListNode reverse(ListNode head) {
        ListNode pre = null;

        while (head != null) {
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }

        return pre;
    }

• 当涉及到用dummy node保存reverse的节点的时候，必须要把前一个node作为pre进入reverse的过程，这样才能够保证dummy node能够指向翻转后的第一个点。

Reverse Nodes in k-group

Find Mid node

用快慢指针

• slow = head, fast = head.next; 无须担心奇偶
• 循环的判断语句fast != null && fast.next != null
• 其他应用
  • 同样可以用于只允许遍历一次的时候
  • 找第nth node, 从头或尾

 public ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

Merge

• 例如交替merge，引入index

 public void merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        int index = 0;

        while (left != null && right != null) {
            if (index % 2 == 0) {
                dummy.next = left;
                left = left.next;
            } else {
                dummy.next = right;
                right = right.next;
            }
            dummy = dummy.next;
            index++;
        }

        //check the remaining list
        if (left != null) dummy.next = left;
        else dummy.next = right;
    }

Split

private RandomListNode splitList(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode temp = head.next;
            head.next = temp.next;
            head = head.next;
            //null check
            if (temp.next != null) {
                temp.next = temp.next.next;
            }
        }
        return newHead;
    }

partition

• 不要忘记第二条list的尾巴节点要指向空，不然就有肯能出现死循环

    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode h1 = dummy1;

        ListNode dummy2 = new ListNode(0);
        ListNode h2 = dummy2;

        while (head != null) {
            if (head.val < x) {
                h1.next = head;
                h1 = h1.next;
            } else {
                h2.next = head;
                h2 = h2.next;
            }

            head = head.next;
        }
        h2.next = null;
        h1.next = dummy2.next;
        return dummy1.next;
    }

Find intersection

跟长度有关，如果有交集，那么长度不同的部分肯定在交集之前。只需要提前移动较长的，使得开始时的长度相同，则肯定能在交集遇到

• getLength，根据length差值，提前移动较长的，直到尾端对齐
• 另一种方法是取两遍iterate，第二次相遇的时候一定在交集起点
• HashTable

Tips

head代表的是第一个节点，不要错误的理解成为一个空的头结点

遍历LL

while (head != null) {
  if (head.val ...)
  ...
  head = head.next;
}

#

对于涉及到第K个的，用first and second比去算index更简单

拼接成新的队列最后

要进行判断，新的队列尾巴是否已经指向null

当要加到LL尾巴

引入指针node来遍历，保持node一直为最后一个元素

每当需要用next.next

包括将fast = head.next等情况，因为fast.next是会用到的，所以必须要排除初始的特殊情况(head == null || head.next == null)