什么是链表

class ListNode {
	public int val; // 节点上存储的元素(data)
	public ListNode next; // 指向下一个节点的指针 public ListNode(int val) {
};

链表类型

1. 单链表

1. 双向链表

1. 单向循环链表

链表操作

1. 添加节点

1. 删除节点

💬 链表常见算法问题

• 判断一个链表是否有环：
• 可以使用快慢指针的方法。

• 找出链表中环的入口节点：
• 可以使用快慢指针的方法，并记录下快指针和慢指针相遇时快指针走过的步数。

• 找出链表中倒数第k个节点：
• 可以使用两个指针，一个指针先走k步，然后两个指针一起走，直到第一个指针到达链表的尾部，第二个指针指向的就是倒数第k个节点。

• 合并两个有序链表：
• 可以使用递归的方法，或者使用迭代的方法。

• 删除排序链表中的重复元素：
• 可以使用快慢指针的方法，并记录下慢指针指向的节点的值。

👣 链表的基本操作

String s = "hello world";

👍 解答思路

• 确认题意和边界条件

• 和出题人沟通思路

• Coding（ 注意code style）

• 测试 - 常见case 和 边界case

• 分析复杂度

• 优化，follow up question

🥊 算法实战

LeetCode 707. 设计链表

1. 与出题人沟通, 确认题意，明确模糊信息，边界条件。

2. 梳理解题思路。

3. Coding。

public class ListNode {
    int val;
    ListNode next;

    public 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++) {
            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) {
        if (index > size) {
            return;
        }
        size++;
        ListNode pred = head;

        for (int i=0; i < index; i++) {
            pred = pred.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pred.next;
        pred.next = newNode;

    }
    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) return;
        index = Math.max(0, index);
        size--;
        ListNode pred = head;

        for (int i=0; i < index; i++) {
            pred = pred.next;
        }

        pred.next = pred.next.next;

    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

1. 测试，常见case 和 边界case。

2. 分析复杂度，优化思路，改造代码。