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
| class MyLinkedList {
private static class Node {
private final int val;
private Node prev;
private Node next;
public Node(int val) {
this.val = val;
}
}
private final Node dummyHead;
private final Node dummyTail;
public MyLinkedList() {
this.dummyHead = new Node(-1);
this.dummyTail = new Node(-1);
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
}
public int get(int index) {
Node node = getNode(index);
return node == null ? -1 : node.val;
}
private Node getNode(int index) {
Node curr = dummyHead;
for (int i = 0; i <= index && curr != null; i++) {
curr = curr.next;
}
if (curr == null || curr == dummyTail) {
return null;
}
return curr;
}
public void addAtHead(int val) {
Node node = new Node(val);
node.next = dummyHead.next;
node.prev = dummyHead;
dummyHead.next.prev = node;
dummyHead.next = node;
}
public void addAtTail(int val) {
Node node = new Node(val);
node.prev = dummyTail.prev;
node.next = dummyTail;
dummyTail.prev.next = node;
dummyTail.prev = node;
}
public void addAtIndex(int index, int val) {
Node curr = dummyHead;
for (int i = 0; i < index && curr != null; i++) {
curr = curr.next;
}
if (curr == null || curr.next == null) {
return;
}
Node node = new Node(val);
node.prev = curr;
node.next = curr.next;
if (curr.next != null) {
curr.next.prev = node;
}
curr.next = node;
}
public void deleteAtIndex(int index) {
Node node = getNode(index);
if (node != null) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
}
|