友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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的节点。
示例：
输入 ["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
提示：
-
0 <= index, val <= 1000 -
请不要使用内置的 LinkedList 库。
-
调用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次数不超过2000。
思路分析
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-22 14:50:41
*/
static class MyLinkedList {
private final ListNode HEAD;
private final ListNode TAIL;
private int size;
public MyLinkedList() {
HEAD = new ListNode(0);
TAIL = new ListNode(0);
HEAD.next = TAIL;
TAIL.prev = HEAD;
size = 0;
}
public int get(int index) {
ListNode node = getNode(index, false);
if (node == null) {
return -1;
} else {
return node.val;
}
}
public void addAtHead(int val) {
addNode(HEAD, val);
size++;
}
public void addAtTail(int val) {
addNode(TAIL.prev, val);
size++;
}
public void addAtIndex(int index, int val) {
ListNode node = getNode(index, true);
if (node != null) {
addNode(node.prev, val);
size++;
}
}
public void deleteAtIndex(int index) {
ListNode node = getNode(index, false);
if (node != null) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
}
private ListNode getNode(int index, boolean lager) {
if (index < 0 || lager ? index > size : index >= size) {
return null;
}
// 如果索引等于链表大小，则直接返回尾部
if (index == size) {
return TAIL;
}
ListNode cur = null;
if (index > size / 2) {
cur = TAIL.prev;
for (int i = 0; i < size - index - 1; i++) {
cur = cur.prev;
}
} else {
cur = HEAD.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
}
return cur;
}
private void addNode(ListNode prev, int val) {
ListNode node = new ListNode(val);
ListNode next = prev.next;
node.next = next;
node.prev = prev;
prev.next = node;
next.prev = node;
}
private static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int x) {
val = x;
}
}
}