一.链表定义

Java

public class ListNode {
    int val;  // 存储的元素
    ListNode next;  // 指向下个节点
    // 无参数构造
    public ListNode();
    // 参数 val 的构造
    public LisNode(int val) {
        this.val = val;
    }
    // 参数 val, node 构造
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.node = next;
    }
}

C++

struct ListNode {
    int val;  // 存储的元素
    ListNode* next;  // 指向下一个节点指针
    ListNode(int x) : val(x), next(NULL) {};  // 节点构造函数 
};

二、设计链表

707. 设计链表

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
}
class MyLinkedList {
    int size; // 链表长度
    ListNode dummy; // 定义一个虚拟头结点，便于操作
    // 初始化链表
    public MyLinkedList() {
        size = 0; // 初始长度为0
        dummy = new ListNode(0); // 虚拟节点则为第0个节点
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) { // 当获取索引非法返回-1
            return -1; 
        }
        ListNode curNode = dummy; // 定义一个当前节点，从虚拟头结点开始遍历
        for (int i = 0; i <= index; i++) {
            curNode = curNode.next; // 每次往后移动一位
        }
        return curNode.val; // 当前节点则为所求节点
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val); // 相当于在虚拟节点后插入一个节点
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val); // 相当于在size这个位置插入节点
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) { // 如果超过size则不添加
            return;
        }
        if (index < 0) { // 如果小于0，则依然指在头部插入
            return;
        }
        size++; // 链表长度增加
        ListNode preNode = dummy; // 定义一个前驱节点
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        ListNode tempNode = new ListNode(val); // 定义一个中间变量节点为要插入的节点
        tempNode.next = preNode.next; // 插入节点的后继为前去的后继
        preNode.next = tempNode; // 前驱节点的后继为要插入节点
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size) { // index无效
            return;
        }
        size--; // 链表长度减少
        ListNode preNode = dummy;
        for (int i = 0; i < index; i++) { // 找到需要删除的节点前驱
            preNode = preNode.next;
        }
        preNode.next = preNode.next.next; // 将要删除节点前驱的后继指向删除节点的后继从而删除当前节点
    }
}