Day07——链表专题

偏执的太偏执、 2024-04-03 12:15 15阅读 0赞

#### 文章目录 ####

*   *   *  14.移除链表元素
         *  15.设计链表

--------------------

#### 14.移除链表元素 ####

我们要删除某个节点必须要知道这个节点的上一个节点，**可以设置一个虚拟头结点位置为cur**，指针cur指向虚拟头节点，如果要删除链表中某个节点，就执行:`cur.next=cur.next.next`,最后返回返回`deumy.next`.

**代码实现:**

class Solution {
        
        public ListNode removeElements(ListNode head, int val) {
        
            ListNode dumny = new ListNode(-1);
            dumny.next = head;
            ListNode cur = dumny;
            while (cur.next!=null){
        
                if(cur.next.val==val){
        
                    cur.next = cur.next.next;
                }else{
        
                    cur = cur.next;
                }
            }
            return dumny.next;
        }
    }

#### 15.设计链表 ####

*  获取链表第index个节点的数值
 *  在链表的最前面插入一个节点
 *  在链表的最后面插入一个节点
 *  在链表第index个节点前面插入一个节点
 *  删除链表的第index个节点

**一定要保证第n个节点为cur.next**

**代码实现：**

//双链表
    class ListNode{
        
        int val;
        ListNode next,prev;
        ListNode() {
        };
        ListNode(int val){
        
            this.val = val;
        }
    }
    class MyLinkedList {
          
    
        //记录链表中元素的数量
        int size;
        //记录链表的虚拟头结点和尾结点
        ListNode head,tail;
        
        public MyLinkedList() {
        
            //初始化操作
            this.size = 0;
            this.head = new ListNode(0);
            this.tail = new ListNode(0);
            //这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
            head.next=tail;
            tail.prev=head;
        }
        
        public int get(int index) {
        
            //判断index是否有效
            if(index<0 || index>=size){
        
                return -1;
            }
            ListNode cur = this.head;
            //判断是哪一边遍历时间更短
            if(index >= size / 2){
        
                //tail开始
                cur = tail;
                for(int i=0; i< size-index; i++){
        
                    cur = cur.prev;
                }
            }else{
        
                for(int i=0; i<= index; i++){
        
                    cur = cur.next; 
                }
            }
            return cur.val;
        }
        
        public void addAtHead(int val) {
        
            //等价于在第0个元素前添加
            addAtIndex(0,val);
        }
        
        public void addAtTail(int val) {
        
            //等价于在最后一个元素(null)前添加
            addAtIndex(size,val);
        }
        
        public void addAtIndex(int index, int val) {
        
            //index大于链表长度
            if(index>size){
        
                return;
            }
            //index小于0
            if(index<0){
        
                index = 0;
            }
            size++;
            //找到前驱
            ListNode pre = this.head;
            for(int i=0; i<index; i++){
        
                pre = pre.next;
            }
            //新建结点
            ListNode newNode = new ListNode(val);
            newNode.next = pre.next;
            pre.next.prev = newNode;
            newNode.prev = pre;
            pre.next = newNode;
            
        }
        
        public void deleteAtIndex(int index) {
        
            //判断索引是否有效
            if(index<0 || index>=size){
        
                return;
            }
            //删除操作
            size--;
            ListNode pre = this.head;
            for(int i=0; i<index; i++){
        
                pre = pre.next;
            }
            pre.next.next.prev = pre;
            pre.next = pre.next.next;
        }
    }