代码随想录-链表 | 707设计链表

LeetCode 707-设计链表

题目链接

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

解题思路

判断：

按照链表的定义书写即可。注意各函数的书写，涉及index时要先判别，

• 索引：index 是否在 [0,this.length) 之间
• 插入：index 是否在[0,this.length] 之间

代码

单链表

class MyLinkedList {public static class Node {int val;Node next;public Node(int val) {this.val = val;this.next = null;}}private Node head;private int length;public MyLinkedList() {this.length = 0;this.head = new Node(0);}public int get(int index) {if (index < 0 || index >= this.length) {return -1;}Node currentNode = this.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(this.length,val);}public void addAtIndex(int index, int val) {if (index > this.length) {return;}Node preNode = this.head;for(int i = 0; i < index; i++) {preNode = preNode.next;}Node newNode = new Node(val);newNode.next = preNode.next;preNode.next = newNode;this.length++;}public void deleteAtIndex(int index) {if (index < 0 || index >= this.length){return;}Node preNode = this.head;for (int i = 0; i < index; i++) {preNode = preNode.next;}preNode.next = preNode.next.next;this.length--;}
}

复杂度

• 时间复杂度
  涉及 index 的相关操作为 O(index), 其余为 O(1)
• 空间复杂度
  O(n)

难点

• 定义链表：要注意初始化链表的长度和头节点。

public MyLinkedList() {this.length = 0;this.head = new Node(0);
}

总结

还是要多熟悉熟悉。