leetcode707-设计链表

原题

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:valnextval 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

示例:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示:

  • 所有val值都在 [1, 1000] 之内。
  • 操作次数将在 [1, 1000] 之内。
  • 请不要使用内置的 LinkedList 库。

解法

思想

链表的数据结构!! 一般会有一个size和一个head,特别注意如果有tail涉及到可能更改tail的地方一定要注意更改tail。(我调试这个bug调试了一个下午?)

代码

class MyLinkedList {
    private class Node{
        public int val;
        public Node next;
    }
    private int size;
    private Node head;
    private Node tail;

    /** Initialize your data structure here. */
    public MyLinkedList() {
        size = 0;
        head = tail = null;
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index>=size || index<0) return -1;
        Node cur = head;
        for(int i = 0;i<index;i++)
            cur = cur.next;
        return cur.val;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        Node newHead = new Node();
        newHead.val = val;
        newHead.next = head;
        if(size==0) tail = newHead;
        head = newHead;
        size++;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {

        Node newTail = new Node();
        newTail.val = val;
        newTail.next = null;
        if(size==0) head = newTail;
        else tail.next = newTail;
        tail = newTail;
        size++;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index>size) return;
        if(index <= 0) {
            addAtHead(val);
            return;
        }
        if(index == size){
            addAtTail(val);
            return;
        } 
        Node node = new Node();
        node.val = val;
        Node cur = head;
        for(int i = 0;i<index-1;i++)
            cur = cur.next;
        node.next = cur.next;
        cur.next = node;
        size++;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index>=size || index <0) return;
        size--;
        if(index == 0) {
            head = head.next;
            return;
        }
        Node cur = head;
        for(int i = 0;i<index-1;i++)
            cur = cur.next;
        cur.next = cur.next.next;
        //这个地方!!! 考虑到可能会把tail删除!!!
        if(index == size){
            tail = cur;
        }
    }
}

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode707-%e8%ae%be%e8%ae%a1%e9%93%be%e8%a1%a8/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月13日 18:05
下一篇 2019年12月15日

相关推荐

  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0130
  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"…

    算法 2019年12月22日
    0120
  • leetcode410-分割数组的最大值

    原题 给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1…

    算法 2020年1月9日
    0580
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i,…

    2020年2月27日
    0250
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130
  • leetcode974-和可被K整除的子数组

    原题 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。 示例: 输入: A = [4,5,0,-2,-3,1], K = 5 输出: 7 解释: …

    算法 2020年5月27日
    0170
  • leetcode64-最小路径和

    原题 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明: 每次只能向下或者向右移动一步。 示例: 输入: [ [1,3…

    算法 2020年2月24日
    0100
  • leetcode841-钥匙和房间

    原题 有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上,对于每个房间 i 都有一…

    2019年12月13日
    0120
  • leetcode86-分隔链表

    原题 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head…

    算法 2020年4月27日
    0140

发表回复

登录后才能评论