训练营Day3
# 203.移除链表元素 (opens new window)
简单题目,主要考察对链表数据结构的熟悉程度。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
if(head.val == val){
head = removeElements(head.next,val);
}else{
head.next = removeElements(head.next,val);
}
return head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 707. 设计链表 (opens new window)
这道题目,主要还是考察链表的结构和虚拟节点头的运用。
但是题目描述的不是很清楚,导致做的时候边界条件不太正确。
后面修改过来了
class MyLinkedList {
int size;
ListNode head; //虚拟头节点
public MyLinkedList() {
this.size = 0;
this.head = new ListNode(0);
}
/**
* 获取第index个节点
* @param index
* @return
*/
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;
}
ListNode currentNode = head;
for (int i=0;i<index;i++){
currentNode =currentNode.next;
}
ListNode node = new ListNode(val);
node.next =currentNode.next;
currentNode.next = node;
size++;
}
public void deleteAtIndex(int index) {
if (index<0 ||index>=size){
return;
}
ListNode currentNode = head;
for (int i=0;i<index;i++){
currentNode =currentNode.next;
}
if (currentNode.next!=null){
currentNode.next = currentNode.next.next;
}
size--;
}
}
class ListNode{
ListNode next;
int val;
ListNode(){}
ListNode(int val){
this.val = val;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
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
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
# 206. 反转链表 (opens new window)
什么叫做熟悉的默认人题
递归就完事了
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
上次更新: 2023/06/09, 17:05:23