707. Design Linked List Medium
1/**
2 * [707] Design Linked List
3 *
4 * Design your implementation of the linked list. You can choose to use a singly or doubly linked list.<br />
5 * A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.<br />
6 * If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
7 * Implement the MyLinkedList class:
8 *
9 * MyLinkedList() Initializes the MyLinkedList object.
10 * int get(int index) Get the value of the index^th node in the linked list. If the index is invalid, return -1.
11 * void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
12 * void addAtTail(int val) Append a node of value val as the last element of the linked list.
13 * void addAtIndex(int index, int val) Add a node of value val before the index^th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
14 * void deleteAtIndex(int index) Delete the index^th node in the linked list, if the index is valid.
15 *
16 *
17 * Example 1:
18 *
19 * Input
20 * ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
21 * [[], [1], [3], [1, 2], [1], [1], [1]]
22 * Output
23 * [null, null, null, null, 2, null, 3]
24 * Explanation
25 * MyLinkedList myLinkedList = new MyLinkedList();
26 * myLinkedList.addAtHead(1);
27 * myLinkedList.addAtTail(3);
28 * myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
29 * myLinkedList.get(1); // return 2
30 * myLinkedList.deleteAtIndex(1); // now the linked list is 1->3
31 * myLinkedList.get(1); // return 3
32 *
33 *
34 * Constraints:
35 *
36 * 0 <= index, val <= 1000
37 * Please do not use the built-in LinkedList library.
38 * At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.
39 *
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/design-linked-list/
44// discuss: https://leetcode.com/problems/design-linked-list/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47#[derive(Clone)]
48struct Node {
49 val: i32,
50 next: Option<Box<Node>>,
51}
52#[derive(Default)]
53struct MyLinkedList {
54 head: Option<Box<Node>>,
55}
56
57/**
58 * `&self` means the method takes an immutable reference.
59 * If you need a mutable reference, change it to `&mut self` instead.
60 */
61impl MyLinkedList {
62 fn print(&self) {
63 let mut cur = match self.head {
64 Some(ref a) => a,
65 None => return,
66 };
67
68 while let Some(ref a) = cur.next {
69 print!("-> {}", a.val);
70 cur = a;
71 }
72 println!()
73 }
74
75 fn new() -> Self {
76 MyLinkedList {
77 head: Some(Box::new(Node {
78 val: -1,
79 next: None,
80 })),
81 }
82 }
83
84 fn get(&self, index: i32) -> i32 {
85 let mut cur = match self.head.as_ref().unwrap().next {
86 Some(ref a) => a,
87 None => return -1,
88 };
89 let mut idx_cur = 0;
90 while idx_cur < index {
91 if let Some(ref next) = cur.next {
92 cur = next;
93 idx_cur += 1;
94 } else {
95 return -1;
96 };
97 }
98 cur.val
99 }
100
101 fn add_at_head(&mut self, val: i32) {
102 let n = Some(Box::new(Node {
103 val,
104 next: self.head.as_mut().unwrap().next.take(),
105 }));
106 self.head.as_mut().unwrap().next = n;
107 }
108
109 fn add_at_tail(&mut self, val: i32) {
110 let mut cur = self.head.as_mut().unwrap();
111 while let Some(ref mut next) = cur.next {
112 cur = next;
113 }
114 cur.next = Some(Box::new(Node { val, next: None }));
115 }
116
117 fn add_at_index(&mut self, index: i32, val: i32) {
118 let mut idx = 0;
119 let mut cur = self.head.as_mut().unwrap();
120 while idx < index {
121 if let Some(ref mut next) = cur.next {
122 cur = next;
123 } else {
124 return;
125 }
126 idx += 1;
127 }
128 cur.next = Some(Box::new(Node {
129 val,
130 next: cur.next.take(),
131 }));
132 }
133
134 fn delete_at_index(&mut self, index: i32) {
135 let mut idx = 0;
136 let mut cur = self.head.as_mut().unwrap();
137 while idx < index {
138 if let Some(ref mut next) = cur.next {
139 cur = next;
140 }
141 idx += 1;
142 }
143 cur.next = cur.next.take().and_then(|a| a.next);
144 }
145}
146
147/**
148 * Your MyLinkedList object will be instantiated and called as such:
149 * let obj = MyLinkedList::new();
150 * let ret_1: i32 = obj.get(index);
151 * obj.add_at_head(val);
152 * obj.add_at_tail(val);
153 * obj.add_at_index(index, val);
154 * obj.delete_at_index(index);
155 */
156
157// submission codes end
158
159#[cfg(test)]
160mod tests {
161 use super::*;
162
163 #[test]
164 fn test_707_1() {
165 let mut obj = MyLinkedList::new();
166 obj.add_at_index(1, 0);
167 obj.print();
168 assert_eq!(obj.get(0), -1);
169 }
170
171 #[test]
172 fn test_707() {
173 let mut obj = MyLinkedList::new();
174 obj.print();
175 obj.get(1);
176 obj.print();
177 obj.add_at_head(2);
178 obj.print();
179 obj.add_at_tail(3);
180 obj.print();
181 obj.add_at_index(1, 2);
182 obj.print();
183 obj.delete_at_index(1);
184 obj.print();
185 obj.add_at_head(0);
186 obj.print();
187 obj.add_at_tail(6);
188 obj.print();
189 obj.add_at_index(1, 1);
190 obj.print();
191 obj.add_at_index(4,4);
192 obj.add_at_index(5,5);
193 obj.print();
194 assert_eq!(obj.get(0), 0);
195 assert_eq!(obj.get(1), 1);
196 assert_eq!(obj.get(2), 2);
197 assert_eq!(obj.get(3), 3);
198 assert_eq!(obj.get(4), 4);
199 assert_eq!(obj.get(5), 5);
200 assert_eq!(obj.get(6), 6);
201 }
202}
203Back
© 2025 bowen.ge All Rights Reserved.