Linked List vs Array

Array, 一组内存里的连续数据

• 能用index访问-->O(1)
• 添加元素直接添加到最后--> O(1) 要考虑到扩容
• 删除元素要挪动后面所有元素位置--> O(n)

Linked List -- 内存中不一定连续

• 不能用index访问 —> O(n)
• 添加元素添加在最好--> O(n)
• 删除需要找到元素位置--> O(n)

public class ListNode {
    public int val;
    public ListNode next;

    public boolean hasNext() {
        return next != null;
    }
    public ListNode(int x) {
        val = x;
        next = null;
    }
    //以下为静态方法
    public static void printNode(ListNode head) {
        System.out.print("->" + head.val);
        if (head.hasNext()) {
            printNode(head.next);
        } else {
            System.out.print("\n");
        }
    }

    public static ListNode buildNode(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode[] nodes = new ListNode[values.length];
        for (int i = 0; i < values.length; i++) {
            nodes[i] = new ListNode(values[i]);
        }
        for (int i = 0; i < values.length - 1; i++) {
            nodes[i].next = nodes[i + 1];
        }
        return nodes[0];
    }
}

一般常用双指针方法

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

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

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

eg. Linked List 找倒数第k个节点
两个指针先隔开k个位置，然后每次相同速度向前进知道快指针出界，慢指针就停留在倒数第k个节点。

递归

第一步和第三步的含义必须相同。
1，寻求子问题解
2，这一层的递归要做什么
3，返回结果

如翻转链表

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode reverseHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return reverseHead;
    }