反转链表 II
做题过程
比反转链表I多了要处理环的问题，但是其实也不需要显式处理，可以用好的代码代替显式处理，这个地方弄得焦头烂额也没弄对。
算法概述
原题
本题要求为反转给出范围内的链表。
JAVA
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
| class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || left == right) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < left - 1; i++) {
prev = prev.next;
}
ListNode curr = prev.next;
ListNode next = curr.next;
for (int i = 0; i < right - left; i++) {
curr.next = next.next;
next.next = prev.next;
prev.next = next;
next = curr.next;
}
return dummy.next;
}
}
|
总结
与 迭代 不同，上述解法可以 保留前驱 ，并且curr是 自动移动 的，只需更新next即可，因为在插入的过程中，区间是固定的，所以前驱是固定的，并且每次操作的对象都是curr之后的节点（往前插入），而curr会逐渐从区间内第一个节点变成最后一个节点。
删除排序链表中的重复元素 II(medium)
做题过程
思路没问题，循环写多了，还没写对，幸好没弄成环，不然更搞笑。
算法概述
原题
本题要求如题所示。一般模拟即可。
JAVA
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
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode current = dummy;
while (current.next != null && current.next.next != null) {
if (current.next.val == current.next.next.val) {
int duplicateVal = current.next.val;
while (current.next != null && current.next.val == duplicateVal) {
current.next = current.next.next;
}
} else {
current = current.next;
}
}
return dummy.next;
}
}
|
总结
current需要从哑结点开始，不然哑结点用来处理初始边界存在重复的意义就不复存在了，而且这样只需要写一个循环（循环内通过记录重复值来辅助删除操作），不用再来一个循环先处理一遍边界情况（我加了dummy还这么写🥲）。控制的是current.next的变化，而不是current变化，重复的直接交给JAVA的垃圾回收机制即可（c++还要delete）。
旋转链表(medium)
做题过程
就想着改下值就行，但其实不行，必须改节点。
算法概述
原题
本题要求为对给出的链表向右旋转（假设循环）给定次数。直接模拟。
JAVA
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
| class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
ListNode t = head;
int length = 1;
while (t.next != null) {
t = t.next;
length++;
}
t.next = head;
k = k % length;
int stepsToNewHead = length - k;
ListNode newTail = head;
for (int i = 1; i < stepsToNewHead; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
|
总结
链表是很 灵活 的，根本不需要动内部的节点，直接动头和尾就行， 节点内部相对关系不需要更改 。
还要注意的是：
k = k % length;：计算实际移动步数t.next = head;：形成环状链表（其实只需要这一步即可，不需要处理索引什么的）ListNode newHead = newTail.next;：形成环之后头尾节点直接相邻，很易于通过其一找到另一个
分隔链表(medium)
做题过程
就是拿个链表存一下大于等于给定值的节点就行了。
算法概述
原题
本题要求为将小于给定值的节点放在大于等于给定值的节点之前（不要改变相对顺序）。就是模拟。
- 时间复杂度为O(n)
- 空间复杂度为O(k)：多少个比给定值大的节点
JAVA
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
|
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy=new ListNode();
dummy.next=head;
ListNode curr=dummy;
List<ListNode> last=new ArrayList<>();
while(curr.next!=null){
if(curr.next.val>=x){
last.add(curr.next);
curr.next=curr.next.next;
}else{
curr=curr.next;
}
}
for (int i = 0; i < last.size(); i++) {
curr.next = last.get(i);
curr = curr.next;
}
curr.next=null;
return dummy.next;
}
}
|
总结
官方题解是 维护两个链表 ，都遍历原链表，但一个链表 只存小于等于给定值的节点 ，另外一个链表存 大于等于给定值的节点 ，遍历完了拼接一下就行了，这样就只是改了一下前驱后驱的相对关系，不用额外的空间复杂度。
