移除链表元素
[代码随想录 移除链表元素](https://programmercarl.com/0203. 移除链表元素.htm)
203. 移除链表元素 - 力扣（LeetCode）
（用时：0.5小时）
普通方法
普通的移除方法中，要将节点分为头结点和非头结点两类。
- 如果头结点就是要移除的元素，那么直接让其next成为头节点即可（即缩头）
- 如果是非头节点，让节点的前一节点的next指向要移除的节点的next即可。
错误
自己也没有想到，普通写的时候还出了好些问题，果然是不熟练啊。
错误：头节点不能用if，也要用while来筛除。
如果用if，那就只判断了一次头节点，那万一头节点的下一个头节点也是要删的呢？（也不知是不是unity的update写多了，写函数的时候脑子里一直是if也会循环hhh）
虚拟头结点法
虚拟头结点就是在原来的头结点前，增加一个头结点，让这个头结点暂时充当头结点。这样就消除头结点的特殊情况，少if判断。
既然消除了头结点的特殊情况，题目也就变成了
重点分析
重点有以下三个：
- while中的判断条件？
- if判断的判断条件？
- if判断成立与否时，要做的操作、分别表示什么？
- currentNode的初始值？
个人的理解如下：
if的判断
先考虑if的判断条件是因为while的判断条件要根据if的逻辑来写。
当currentNodex.val等于要找的val移除当前节点，让需移除节点的前驱节点的next等于其下一节点（即frontNode.next = currentNode.next）。注意这里是知道需移除节点的前驱节点的，而这里用的又是单向链表，那就只有“未雨绸缪”，在它的前驱节点时就判断它是否要被移除，要的话让前驱节点实施才行。
不等于时，继续遍历。
currentNode的初始值
currentNode的初始值就很简单了，根据前面这里的if判断，初始值应该是虚拟节点。
while中的判断条件？
所有的节点都是一类了，那么就只有这一个while了。while里的条件必定是让currentNodex停下来不继续遍历的。问题在于是currentNode还是currentNodex.next不等于null。
单独看while，这里两者好像都可以。但是我们得配合里面的if。if判断的是currentNode.next.val是否为0，这个currentNode.next必须要是非null，.val才能引用，不然会报错。所以条件是currentNode.next!=null。
代码实现
普通方法：
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
|
public ListNode RemoveListElementFun2(ListNode head, int val)
{
while (head != null && head.val==val)
{
head = head.next;
}
ListNode currentNode = head;
while (currentNode!=null && currentNode.next != null)
{
if (currentNode.next.val == val)
{
currentNode.next = currentNode.next.next;
}
else
{
currentNode = currentNode.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
|
public ListNode RemoveListElementFun(ListNode head, int val)
{
ListNode visHeadNode = new ListNode(val+1, head);
ListNode currentNode = visHeadNode;
while (currentNode.next!=null)
{
if (currentNode.next.val==val)
{
currentNode.next = currentNode.next.next;
}
else
{
currentNode = currentNode.next;
}
return visHeadNode.next;
}
}
|
设计链表
代码随想录 设计链表
707. 设计链表 - 力扣（LeetCode）
（用时：1.5小时）
思路分析
这道题是设计类的题目。设计“类”的话，方法和思路就很多了。所以写的时候就老是在优化，觉得这里能写的更好，然后就写了好久。。。（怎么有点职业病的感觉hhh）
这道题就是对链表的增删查改。增删改都要在查的基础上，但是题目需要实现的函数只是给定下标，返回值就好，这在数组的增删改上挺好的（数组的查也就是下标引用hhhh），但在链表上，就有点鸡肋了。于是最开始先写了个查的函数，给定下标，返回指向该节点的指针（不知道会不会有什么内存方面的浪费？以往写类都不是为了不是很注重算法的东西，写的又不是c++，对这方面不是很敏感）
删和改的函数没什么好说的，主要就是利用这个查的函数。
增的函数，可考虑的就多了。总所周知链表的插入有头插和尾插两种。刚开始写的时候没有想到虚拟头节点的运用，就用头插和尾插的角度进行了分析。后来进行了迭代，增加了虚拟头结点，不分什么头插尾插了。
01：定义三个函数。（如果没有虚拟节点，那么最简洁方便的就是这样）
第一个，查找节点函数。给定index，返回指向第index个节点的指针。
第二个，头插法函数。给定index，在该index前面插入新节点
第三个，尾插法函数。给定index，在该index后面插入新节点。
插入节点分为三种情况：
1.增加头结点：在原来的头结点上用头插法；
2.增加尾节点：在原来的尾节点上用尾插法；
3.中间的节点：自主选择是在第index个节点上用头插还是尾插）
02：定义两个函数。这里省略了头插法的函数，因为有了虚拟节点。
第一个，同上
第二个，尾插法函数。同上
有了虚拟头结点，插入节点的三种情况的思路稍微改变了：
1.增加头结点：在虚拟头结点处用尾插法；
2.增加尾节点：在原来的尾节点上用尾插法；
3.中间的节点：自主选择。若在index前面插入，则在index-1上用尾插法。若在index后面插入，则在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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
| public class MyLinkedList
{
public class MyListNode
{
public int val;
public MyListNode next;
public MyListNode(int val = 0, MyListNode next = null)
{
this.val = val;
this.next = next;
}
}
public MyListNode visHeadNode;
public int listSize;
public MyLinkedList()
{
visHeadNode = new MyListNode(0, null);
}
public MyListNode FindNode(int index)
{
if (index<-1 || index>=listSize)
{
return null;
}
MyListNode p = visHeadNode;
while (index > -1)
{
p = p.next;
index--;
}
return p;
}
public void HeadInsertion(int index,int val)
{
MyListNode indexFrontNode = FindNode(index - 1);
if (indexFrontNode == null)
{
return;
}
MyListNode newNode = new MyListNode(val, indexFrontNode.next);
indexFrontNode.next = newNode;
listSize++;
}
public void TailInsertion(int index,int val)
{
MyListNode indexNode = FindNode(index);
if (indexNode == null)
{
return;
}
MyListNode newNode = new MyListNode(val, indexNode.next);
indexNode.next = newNode;
listSize++;
}
public int Get(int index)
{
MyListNode indexNode = FindNode(index);
return indexNode == null ? -1 : indexNode.val;
}
public void AddAtHead(int val)
{
TailInsertion(-1, val);
}
public void AddAtTail(int val)
{
TailInsertion(listSize-1, val);
}
public void AddAtIndex(int index, int val)
{
TailInsertion(index - 1, val);
}
public void DeleteAtIndex(int index)
{
if (index<0 || index>=listSize)
{
return;
}
if (index==0)
{
visHeadNode.next = visHeadNode.next.next;
}
else
{
MyListNode indexFrontNode = FindNode(index - 1);
indexFrontNode.next = indexFrontNode.next.next;
}
listSize--;
}
public void PrintList()
{
MyListNode p = visHeadNode.next;
Console.Write("目前的链表：");
while (p!=null)
{
Console.Write(p.val + " ");
p = p.next;
}
Console.WriteLine();
}
}
|
反转链表
代码随想录 反转链表
206. 反转链表 - 力扣（LeetCode）
（用时：0.5小时）
双指针法
单向链表的节点的前驱节点自己是不知道的，因此在遍历和更改的时候，需要定义多个指针，防止断链的情况。画图分析：
随意找中间的某个节点进行翻转，发现至少需要一个cur指针用于向前遍历，front指针记录cur的前驱节点以及一个back指针记录后驱节点防止反转后cur无法进行遍历（看视频的时候，也有说back是临时的，所以不算第三个指针。)
重点分析
这道题有几个需要注意的重点：
- back指针记录cur后驱节点应在改变cur指针next朝向前进行，不然会cur处断链，cur后续无法继续遍历。
- front指针的更新应该在cur指针的更新之前，因为此时的front指针的next已经这次循环之前就被改了朝向。
递归法
能够被循环迭代实现的，一般都能写成递归。
这道题由于已经给出了调用函数的定义，因此无法在其基础上改成递归函数。定义一个新的函数，用于处理递归的逻辑。
- 递归的参数：递归函数的参数是要一直改变的值。在循环中，cur和 front的值一直在更新（back是临时的），因此递归的参数就是cur和front。
- 递归的出口：递归函数的出口就是循环终止的条件。在循环中，while的终止条件是cur为null，因此这就是递归的出口。
- 递归要处理的逻辑：递归的逻辑就是循环要做的东西。在循环中，其实是一直重复着临时指针back指向cur后驱节点、改变cur的next朝向和front、cur更新的操作。那在递归了也如此，只是注意front、cur的更新要在给递归函数传参时体现。
代码实现
双指针法：
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
|
public ListNode ReverseListFun1(ListNode head)
{
ListNode frontNode, curNode, backNode;
frontNode = null;
curNode = head;
while(curNode != null)
{
backNode = curNode.next;
curNode.next = frontNode;
frontNode = curNode;
curNode = backNode;
}
return frontNode;
}
|
递归法：
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
|
public ListNode ReverseListFun2(ListNode head)
{
return Reverse(null, head);
}
public ListNode Reverse(ListNode frontNode,ListNode curNode)
{
if (curNode==null)
{
return frontNode;
}
else
{
ListNode backNode = curNode.next;
curNode.next = frontNode;
return Reverse(curNode, backNode);
}
}
|
