leetcode_day3
本文最后更新于 2024年8月18日 下午
203.移除链表元素
看见链表跟回家一样,大一走来就研究链表,被->
和.
的用法confuse了好久,然后链表操作信手拈来,现在实现个线性表、栈、队列都是拿链表来实现,数组都不会写了……
题很简单,拿java练练语法好了,就连java都是一把过: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode h = new ListNode();
h.next = head;
ListNode cur = h;
while(cur.next != null) {
if(cur.next.val == val) {
cur.next = cur.next.next;
}
else
cur = cur.next;
}
return h.next;
}
}
707.设计链表
群友遇到问题,跟着debug了一会,本来不想做的,给出修改后的群友代码吧,收获也有
1 |
|
就是这上面俩是等效的,不够之前知道,算加深印象吧,毕竟while(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
71class MyLinkedList {
public:
struct LNode{
int val;
LNode* next;
LNode(int v):val(v),next(nullptr){} //构造函数
// LNode(int v){ val=v,next=nullptr;}
};
MyLinkedList() {
//建立空链表
lsize=0;
lhead=new LNode(0);
}
int get(int index) {
if(index<0 || index>=lsize) return -1;
LNode* p=lhead;
//从第一个实际数据开始遍历,当循环结束,一定是p指向了Index位置
while(index--)
p=p->next;
p=p->next;
return p->val;
}
void addAtHead(int val) {
//将val插入作为第一个节点,即头结点的下一个
LNode* np=new LNode(val);
np->next=lhead->next;
lhead->next=np;
lsize++;
}
void addAtTail(int val) {
//在最后增加节点
LNode* np=new LNode(val);
LNode* p=lhead;
while(p->next!=nullptr){
p=p->next;
}
np->next=p->next;
p->next=np;
lsize++;
}
void addAtIndex(int index, int val) {
if(index>lsize) return;
if(index == lsize) {
addAtTail(val);
return;
}
LNode* np=new LNode(val);
LNode* p=lhead;
while(index--)
p=p->next;
np->next=p->next;
p->next=np;
lsize++;
}
void deleteAtIndex(int index) {
if(index<0 || index>=lsize) return;
LNode* p=lhead;
while(index--)
p=p->next;
LNode* tmp=p->next;
p->next=p->next->next;
delete tmp;
lsize--;
}
private:
int lsize;
LNode* lhead;
};
206.反转链表
主要看了下递归做法,对于递归还是很迷,这次也没有一次写出来。
将后续部分看作已经反转完成,所以当前节点的下一个节点的下一个应该变成当前,即:
cur->next->next = cur;
对于头节点,再加一个next指null,就完成了。 1
2
3
4
5
6
7
8
9
10class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode * virHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return virHead;
}
};