移除列表元素
link：203. 移除链表元素 - 力扣（LeetCode）
首先单向链表是有一个数据域和指针域且在内存中不连续.
链表的查找需要从头往后一个个查找【时间复杂度为O(n)】，但是数组查找只需要访问对应元素下标即可【时间复杂度为O(1)】.
查找频繁：数组是更好的选择，因为通过索引访问的时间复杂度是 O(1)，链表则需要遍历.
插入/删除频繁：链表更适合，因为它可以高效地插入和删除元素，时间复杂度为 O(1)（假设已找到插入或删除位置）。相反，数组在插入和删除时需要移动大量元素，时间复杂度为 O(n).
思路分析
看到题目最第一反应就是常规解法，遍历链表找到target直接进行删除操作.【目标是头节点和不是头节点两种情况】（其实还是想有更优雅的解法 不用单独处理移除头节点的情况）
直接删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
ListNode cur = head.next;
ListNode prev = head;
while(cur != null){
if(cur.val == val){
prev.next = cur.next;
cur = cur.next;
}
else{
prev = cur;
cur = cur.next;
}
}
if(head.val == val){
head = head.next;
}
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
25
26
27
28
29
30
31
|
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null) {
return head;
}
ListNode dummyNode = new ListNode(-1,head);
ListNode cur = dummyNode;
ListNode prev = head;
while(prev != null) {
if(prev.val == val) {
cur.next = prev.next;
}else {
cur = prev;
}
prev = prev.next;
}
return dummyNode.next;
}
}
|
设计链表
link：707. 设计链表 - 力扣（LeetCode）
综合练习链表五大操作的好题目！
1.获取链表的index下标节点数值.
2.在链表最前面插入节点.
3.在链表最后插入节点.
4.在链表第index个节点前插入节点.
5.删除链表第index个节点.
思路分析
先从链表需要的元素入手，head，tail，size.
考虑虚拟头节点.【优先考虑特殊情况】
个人觉得对于单链表更容易操作.(好吧其实就是一个懒蛋😂)
单链表
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
| class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
int size = 0;
head = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
for(int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.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;
}
if(index < 0) {
index = 0;
}
size++;
ListNode prev = head;
for(int i = 0; i < index ;i++) {
prev = prev.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = prev.next;
prev.next = toAdd;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size) {
return;
}
size--;
ListNode prev = head;
for(int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = prev.next.next;
}
}
|
双链表
用双链表操作时需要注意指针操作的逻辑.
head.next = tail;
tail.next = head;
index < (size - 1) / 2 判断用来决定是从头节点还是尾节点进行遍历，这样做是为了提高查找效率
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
| class MyLinkedList {
class ListNode {
int val;
ListNode next,prev;
ListNode(int x) {val = x;}
}
int size;
ListNode head,tail;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int index) {
if(index < 0 || index >= size){return -1;}
ListNode cur = head;
if(index < (size - 1) / 2){
for(int i = 0; i <= index; i++){
cur = cur.next;
}
}else{
cur = tail;
for(int i = 0; i <= size - index - 1; i++){
cur = cur.prev;
}
}
return cur.val;
}
public void addAtHead(int val) {
ListNode cur = head;
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next.prev = newNode;
cur.next = newNode;
newNode.prev = cur;
size++;
}
public void addAtTail(int val) {
ListNode cur = tail;
ListNode newNode = new ListNode(val);
newNode.next = tail;
newNode.prev = cur.prev;
cur.prev.next = newNode;
cur.prev = newNode;
size++;
}
public void addAtIndex(int index, int val) {
if(index > size){return;}
if(index < 0){index = 0;}
ListNode cur = head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next.prev = newNode;
newNode.prev = cur;
cur.next = newNode;
size++;
}
public void deleteAtIndex(int index) {
if(index >= size || index < 0){return;}
ListNode cur = head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
cur.next.next.prev = cur;
cur.next = cur.next.next;
size--;
}
}
|
