线性表

目录

习题

• 2.3.3
• 2.3.7

总结

• 对于链表,经常采用的方法有头插法、尾插法、逆置法、归并法、双指针法等,对具体问题需要灵活变通;
• 对于顺序表,由于可以直接存取,经常结合排序和查找的几种算法设计思路进行设计,如归并排序、二分查找等。

链表中的临时指针变量

在链表相关的算法中，经常遇到的一个问题是我们需要引入一个临时变量用来保存结点指针，防止“断链^[1]”，结合书中给出的具体代码，可以总结出以下两点：

1. 当结点指针后移，原结点保留时:
   例如q13这道题目中

r = p1->next; // 暂存，防止断链
p1->next = L1->next;
L1->next = p1;
p1 = r;

2. 当结点指针移动，原结点释放时:

例如q15中

while (pb) {
    u = pb;
    pb = pb->next;
    free(u);
}

可以看出区别在于前者中临时变量保存的是next，而后者中保存的是p当前，个人觉得这样区别主要在第二点上，因为若按如下方式书写代码

while (pb) {
    u = pb->next;
    free(pb);
    pb = u;
}

虽然原理上来说也没问题但是free(pb);在笔试中可能语义性上给人的感觉就是"这里可能会断链"，所以我们尽量不要这样写

双指针的妙用

• 在q21中，借用双指针求得环的入口
• 在q25中，巧用双指针得到链表的中间结点

提示

设置双指针不同的移动速度，很巧妙

---

1. 链表的结构，是一个指向下一个结点的，若中间一个结点的next指向出问题，则后续的结点都无法访问 ↩︎