【 LeetCode 】 design list

 

链表操作的两种方式：

1. 直接使用原来的链表来进行操作.
2. 设置一个虚拟头结点在进行操作.

下面采用的设置一个虚拟头结点.

Singly linked list method

//定义链表
class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){this.val = val;}
    ListNode(int val,ListNode next){this.val = val;this.next = next;}
}


//单链表
class MyLinkedList {
    int size; //链表中元素个数
    ListNode dummyHead; //虚拟头结点

    public MyLinkedList() { //初始化链表
        size = 0;
        dummyHead = new ListNode(0);
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode cur = dummyHead; // 或者ListNode cur = dummyHead.next;
        for(int i = 0;i <= index;i++){ //或者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) {
    // 在第index个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点.
    // 如果index 等于链表的长度,则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度,则返回空
        if(index > size){
            return;
        }
        if(index < 0){
            index = 0;
        }
        //size++;
        //找到要插入节点的前驱,要在第nInsert a contact before each node,要找到第n个节点的前驱
        ListNode pre = dummyHead;
        for(int i = 0; i < index;i++){ //找第n个节点的前驱节点,没有=
            pre = pre.next;
        }
        ListNode add = new ListNode(val);//Set the node to add
        add.next = pre.next; //Setting the node order is important,Set the next node of the newly added node first（即第n个节点）
        pre.next = add; //Then set the firstn个节点的后继节点,If set in reverse,then the next node of the newly added node cannot be found（即第n个节点）
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        //size--;
        ListNode pre = dummyHead;
        for(int i = 0;i < index;i++){ //找第n个节点的前驱节点,没有=
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;
    }
}


/**
 * 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);
 */

Doubly linked list method

//双链表
class MyLinkedList {
    class ListNode{
        int val;
        ListNode next,prev;
        ListNode(int x){val = x;}
    }
    int size;
    ListNode head,tail;//定义头指针和尾指针

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode cur = head;
        //通过判断index <(size-1)/2To determine whether to traverse from the head node or the tail node,提高效率
        if(index < (size - 1) / 2){
            for(int i = 0;i <= index;i++){
                cur = cur.next;
            }
        }else{
            cur = tail;
            for(int i = 0;i <= size - 1 - index;i++){
                cur = cur.prev;
            }
        }
            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;}
        if(index < 0){index = 0;}
        ListNode pre = head;

        for(int i = 0;i < index;i++){
            pre = pre.next;
        }
        ListNode add = new ListNode(val);
        add.next = pre.next;
        pre.next.prev = add;
        pre.next = add;
        add.prev = pre;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){return;}
        ListNode pre = head;

        for(int i = 0;i < index;i++){
            pre = pre.next;
        }
        //pre.next = pre.next.next; 先写这个->错误
        pre.next.next.prev = pre; //It is important to set this first,不然无法找到pre.next,Same as the one above
        pre.next = pre.next.next;
        size--;
    }
}



/**
 * 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);
 */