题目描述
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类:
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效,则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度,那么该节点会被追加到链表的末尾。如果index比长度更大,该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效,则删除链表中下标为index的节点。
示例:
输入: ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]]
输出: [null, null, null, null, 2, null, 3]
解释:
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在,链表变为 1->3
myLinkedList.get(1); // 返回 3
思路分析
1. 总体思路
先在类里面创建结构体,制造链表所包含的要求,再分析每一个函数所要求的,最后析构即可。
2. 实现细节
1. 结构体设置
设置结构体的时候,要设置一个有参构造,以应对新的 ListNode 的插入,同时要在结构体外部设置一个头指针 head 和用来表示链表大小的 size。
2. get 部分
首先要注意的是,判断 index 是否合法的条件是 <0 和 >=size,这里的 >=size 是因为我们的链表是从 0 开始,末尾的那个链表部分的序号是 size-1,接下来就是用 cur 指针遍历了。
3. addAtHead 部分
这里要注意的是这两行代码不能颠倒顺序,因为颠倒后 newNode->next 指向不了你所需的先前的 head。
newNode->next = head;
head = newNode;

