LeetBook 刷题笔记：链表（一）

• 与数组相似，链表也是一种线性数据结构。
• 链表有两种类型：单链表和双链表。
• 链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
• 单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。
  • 通过这种方式，单链表将所有结点按顺序组织起来。
  • 单链表中结点的典型定义：

    public class SinglyListNode {
        int val;
        SinglyListNode next;
        SinglyListNode(int x) { this.val = x; }
    }
    

  • 在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
  • 与数组不同，我们无法在常量时间内访问单链表中的随机元素。
    • 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。
    • 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

• 如果我们想在给定的结点 prev 之后添加新值，我们应该：
  • 使用给定值初始化新结点 cur；
    
  • 将 cur 的 next 字段链接到 prev 的下一个结点 next；
    
    • 将 prev 中的 next 字段链接到 cur。
      
• 与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

• 如果我们想从单链表中删除现有结点 cur，可以分两步完成：
  • 找到 cur 的上一个结点 prev 及其下一个结点 next；
    
  • 接下来链接 prev 到 cur 的下一个节点 next。
    
• 在我们的第一步中，我们需要找出 prev 和 next。
  • 使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。
  • 因此，删除结点的时间复杂度将是 O(N)。
  • 空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

• 设计链表的实现。
  • 可以选择使用单链表或双链表。
  • 单链表中的节点应该具有两个属性：val 和 next。
  • val 是当前节点的值，next 是指向下一个节点的指针/引用。
  • 如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。
  • 假设链表中的所有节点都是 0-index 的。
• 在链表类中实现这些功能：
  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
• 提示：
  • 所有val值都在 [1, 1000] 之内。
  • 操作次数将在 [1, 1000] 之内。
  • 请不要使用内置的 LinkedList 库。

• 示例：
  • MyLinkedList linkedList = new MyLinkedList();
  • linkedList.addAtHead(1);
  • linkedList.addAtTail(3);
  • linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
  • linkedList.get(1); //返回2
  • linkedList.deleteAtIndex(1); //现在链表是1-> 3
  • linkedList.get(1); //返回3

public class ListNode {
    int val;
    ListNode next; // 后驱节点
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    int size; // 记录链表长度
    ListNode head; // 虚拟头节点
    public MyLinkedList() { // 初始化
        size = 0;
        head = new ListNode(0);         
    }
    
    public int get(int index) {
        if (index >= size || index < 0) {
            return -1;
        }
        ListNode cur = head;
        for(int i = 0; i <= index; i++) { // 因为有虚拟头节点,查找 index+1 位置。
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
    	// index 大于 size 直接返回
        if (index > size) {
            return;
        }
        // index<0, 根据题意在头部插入节点
        if (index < 0) {
            index = 0;
        }
        ++size; // 添加了节点记得链表的长度要加一。
        ListNode pre = head;
        // 遍厉找到要添加节点位置的前一个节点
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        // 创建新的节点
        ListNode toAdd = new ListNode(val);
        toAdd.next = pre.next;
        pre.next = toAdd;
    }
    
    public void deleteAtIndex(int index) {
    	 // 因为 index 从零开始,所以 index=size 时也是越界了。
        if (index < 0 || index >= size) {
            return;
        }
        --size; // 删除节点记得链表长度减一
        ListNode pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}