707.设计链表
题目
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：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 的节点。
提示：
- 0 <= index, val <= 1000
- 请不要使用内置的 LinkedList 库。
- 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。
思路
本题所涉及的都是链表的基础操作：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
采用前一道题所使用的虚拟头结点操作，可以使操作保持一致性。
解法
单链表解法
代码示例：
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val) { this.val=val; } } class MyLinkedList { int size; ListNode head; public MyLinkedList() { size = 0; head = new ListNode(0); } public int get(int index) { if (index < 0 || index >= size) { return -1; } ListNode currentNode = head; for (int i = 0; i <= index; i++) { currentNode = currentNode.next; } return currentNode.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; } size++; ListNode pred = head; for (int i = 0; i < index; i++) { pred = pred.next; } ListNode toAdd = new ListNode(val); toAdd.next = pred.next; pred.next = toAdd; } public void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; } size--; if (index == 0) { head = head.next; return; } ListNode pred = head; for (int i = 0; i < index ; i++) { pred = pred.next; } pred.next = pred.next.next; } }
- 时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
- 空间复杂度: O(n)
双链表解法
代码示例：
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); head.next=tail; tail.prev=head; } public int get(int index) { if(index<0 || index>=size){ return -1; } ListNode cur = this.head; if(index >= size / 2){ 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) { 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; } 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; } }
- 时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
- 空间复杂度: O(n)
