【LeetCode】设计链表

 

链表操作的两种方式：

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

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

单链表方法

//定义链表
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++;
        //找到要插入节点的前驱，要在第n个节点前插入接点，要找到第n个节点的前驱
        ListNode pre = dummyHead;
        for(int i = 0; i < index;i++){ //找第n个节点的前驱节点，没有=
            pre = pre.next;
        }
        ListNode add = new ListNode(val);//设置要添加的节点
        add.next = pre.next; //设置节点顺序很重要，先设置新添加节点的后一个节点（即第n个节点）
        pre.next = add; //然后再设置第n个节点的后继节点，如果反过来设置，则找不到新添加节点的后一个节点（即第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);
 */

双链表方法

//双链表
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)/2来判断是从头结点还是尾节点遍历，提高效率
        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; //先设置这个很重要，不然无法找到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);
 */