¶链表相关实操
¶概述
- 在链表的操作中，理解链表指针的概念很重要；C语言的指针代表的意思是对象的内存地址，在Java对应的概念则是引用；将对象赋值给变量 ，实际是将对象的内存地址赋值给了变量，用来定位对象在内存中的位置。
- 为了更深入地理解这些概念和链表结构，通过：反转单链表，合并有序单链表，检测链表环，删除链表倒数第N个节点这四个实践场景来加深印象。
¶反转单链表
给定链表 a -> b -> c -> d-> e ，反转成 e -> d-> c-> b-> ->a ,并返回头节点
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
static class Node {
Object value = null;
Node next;
public Node(Object value) {
this.value = value;
}
}
//反转单链表
public void reverseLinkList(Node head){
Node first = new Node(null);
first.next = head;
while(true){
if(head.next == null){
break
}
Node move = head.next;
Node moveNext = head.next.next;
//修改指针引用
head.next = moveNext;
move.next = first.next;//链接到第一个非空节点
first.next = move; // move 成为第一个非空节点
}
//输出
while(first.next!=null){
printf(first.next.value + " ---> ")
first = first.next;
}
printf("null");
}最开始想到的思路是：
这个思路导致我陷入怎么控制外层循环的问题中，为了在合适的时候结束循环，将事先记录的尾节点和当前头节点对比，代码逻辑混乱没有实现出来
现在的这个思路，其实就是通过增加带头节点控制整条链表的第一个节点的位置；每次操作都看作是将第二个节点插入到都头节点和第一个节点之间，当第一个节点指向空，说明链表已经反转完成
¶删除链表倒数第N个节点
因为链表是无法通过索引定位元素的，所以删除倒数第N个节点需要再遍历的时候记录当前节点的索引位置，尝试实现一下
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
//删除链表倒数第N个节点
public static void delNIndexNode(Node head, int n) {
/**
* 1. 假设链表长度为k, 需要进行 k-n 次遍历才能到达 n 节点位置
* 2. 但是此时也并不知道那是第 n 个节点
*/
Node first = head;
Node snode = head;
int i = 0;
while (true) {
head = head.next; // n 次执行
i++; // n 次执行
if (head.next == null) { // n 次
int k = i-n;
while(first.next !=null){ //k 次
first=first.next; // k 次
k--;
if(k==0){
Node del = first.next;
Node next = first.next.next;
//删除节点
first.next = next;
del.next=null;
break;
}
}
break;
}
}
while (snode!= null) {
System.out.print(snode.value + " ---> ");
snode = snode.next;
}
System.out.print("null");
}最开始的思路是反转链表，然后 n – 去删除节点，但是为了维持链表本身的顺序，还得再次反转，觉得应该不是好办法
不定长的链表，要获取倒数第N个，不仅得到达倒数第N个位置；还得知道这是倒数第N个节点；
因为没想到其他办法，还是先遍历获得链表长度 k ,正序的删除位置就是 i = k - n; 再 i – 进行正序遍历删除；
觉得这个应该也不是最优解，先遍历让长度已知再去正序遍历感觉解法太普通
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//再次尝试简化代码
public static void delNNodeNew(Node head,int n){
Node first = head;
Node snode = head;
while(true){
//将 n 减少到负数
if(head.next!=null){
n--;
head = head.next;
}else{
//得出正序的位置
if(n <0){
n=-1*n;
}
while(n!=0){
first = first.next;
n--;
}
Node del = first.next;
Node next = first.next.next;
//删除节点
first.next = next;
del.next=null;
break;
}
}
System.out.println(snode);
}相比之前的那种实现，少了 i 和 k 的计数赋值，但还是得经历一次遍历才能知道正序的位置，也不是最优解，参考了一下正确答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public static Node deleteLastN(Node head, int n) {
if(n < 1 || head == null) {
return head;
}
Node guard = new Node('/');
guard.next = head;
Node slow = guard;
Node fast = guard;
//先将快指针移动k-1次
for(int i = 0; i < n; i++) {
if(fast != null) {
fast = fast.next;
}
}
//快慢指针一起前进，当快指针到达队尾，慢指针所在位置就是的下一个节点就是需要删除的节点
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return guard.next;
}一个指针遍历定位不到n的位置，所以需要将问题转换成用相对距离确定n的位置，结束条件就是距离链表尾部n长的节点就是第n个节点
自己的思路还是没有开阔起来，偏向于常规思考模式，值得警惕
¶合并有序单链表
合并有序单链表要确保合并后的单链表也是有序的，以A链表为基准，用B链表去合并，需要小心每次插入一个B节点到A链表中，不能丢失B链表的余下节点
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
static class Node<E extends Comparable> {
E value = null;
Node next;
public Node(E value) {
this.value = value;
}
public boolean compare(Node<E> that){
return this.value.compareTo(that.value)>=0;
}
}
//合并有序单链表
public static void mergeLink(Node<Integer> headA,Node<Integer> headB){
Node<Integer> firstA = new Node<>(null);
firstA.next=headA;
Node<Integer> firstB = new Node<>(null);
firstB.next=headB;
Node<Integer> temp = headB;
Node<Integer> tb = headA;
while(temp!=null){
//需要判断A链是否到了尾部
if(tb.next !=null && tb.next.compare(temp)){
// A 的节点大于 B 头节点，B需要插入到头部
//保持B链不断
firstB.next = temp.next;
//B 插入A 链
temp.next=tb.next;
tb.next=temp;
}else{
// A 节点 < B
if(tb.next==null && !tb.compare(temp)){
tb.next=temp;
break;
}
tb = tb.next;
}
temp = firstB.next;
}
System.out.println(firstA);
}确定跳出循环的条件是一条链表中的节点已经遍历完毕，最开始的是实现在第26行少了A链表到达尾部的判断，导致B链表的最后一个数被跳过
这里也需要处理极端的情况，如果A链遍历一次之后，发现A链的尾节点大于B链的头节点，直接将整条B链插入到A链表中即可
¶检测链表环
这个因为我之前了解了思路是用快慢指针实现的，所以等于是看到了答案
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
public static void checkaLinkCycle(Node head){
Node slow = head;
Node fast = head.next;
//如果链表存在环，快指针就会一直绕圈，直到在【某一圈】追上慢指针
while(fast.next!=null){
if(slow.next.equals(fast.next)){
System.out.println(true);
return;
}else{
slow=slow.next;
fast=fast.next.next;
}
}
System.out.println(false);
}
public static void main(String[] args) {
Node a = new Node(1);
Node b = new Node(3);
Node c = new Node(5);
Node d = new Node(7);
Node e = new Node(2);
Node f = new Node(4);
Node h = new Node(6);
Node i = new Node(8);
a.next = b;
b.next = c;
c.next = d;
d.next=e;
e.next = f;
f.next=h;
h.next=i;
i.next=a;
checkLinkCycle(a);
}这个问题没有太多的思考过程，因为提前知道了解法就是快慢指针
关于快慢指针的步长：
- 在环形链表中，慢指针始终以 1 的速度前进
- 快指针以 N 倍于慢指针的速度前进
- 快指针最少前进了多少步才会恰好与慢指针相遇 ?
- 我用上面的代码做了测试，将快指针分别取 2 ，4，6，8倍步长，计数循环的次数分别是:7 , 5，3，1。结论就是快慢指针步长差刚好是一倍链表长度快指针可以 1步 追上慢指针；
- 那么问题来了：链表多长? 不知道，链表都是引用关联起来的，长度属性对于它的应用场景不那么重要。因此快指针取 2倍 慢指针的步长，可以保证它一定会追上慢指针
¶小结：
- 链表的操作中，需要注意的就是指针丢失，在改变节点指针的时候，a-b-c,将d插入到b，c之间； **操作顺序一定是先确保c节点不会丢失，先将d指向c，再将b指向d，结果就是 a-b-d-c **；
- 如果是像合并有序单链表这样的操作，就得注意维持被移除了节点的链表的引用不丢失:
- A链: a-b-c-d ; B链: e-f-g-h
- e 插入到 a，b之间 ：
- e.next = a.next ; a.next = e ; 这种操作就是错的，因为 e.next = f , 直接改变 e.next 的指向会导致 B链丢失
- 先添加指向B链头部的 firstB -> e;将 e 插入 a，b的操作顺序就是:
- firstB.next = e.next ; //保证B链的引用还在
- e.next = a.next ; a.next = e
- 链表的操作中稍微没有兼容到边界情况的话，例如空链表，单节点链表等，换个例子就跑不通了