我们能否给一个无环链表建环呢？其实貌似也不很难，只要找到最后一个结点 tail，让它指向环的入口就行。所以问题分解为：找到环入口点 cur，把最后的指针 tail 指向 cur即可。首先找到环入口，也就是参数 num。定义工作指针 LinkList cur = *L; 让它遍历到 num 的位置。这个时候让第二个工作指针 tail 接替 cur 遍历到末尾。

阅读全文 >>

昨天介绍了单链表逆序的两种方法，后来我又想到了第三种。我们就是要深入地研究每个细节嘛。这个方法比较简单，这里就直接上函数了。重新建立一个单链表newList，每次将list中的第一个结点放到newList后面。注释比较详细，所以就不具体说了。

阅读全文 >>

昨天我们谈到了头插法，可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。与头插法区别下？*L 是头结点，r这里的角色是尾结点，一开始他们是重合的。

阅读全文 >>

不知道有没有注意到，前面我们在谈“单链表插入操作”的时候，其实我们是用插入操作来完成了单链表的整表创建的。那么创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。其实就是将 p->next 指向结点 (*L)->next，然后再将 结点 (*L)的后继指向p，这个很好理解。

阅读全文 >>

这里也同样需要用到“工作指针”。首先声明一个工作指针，并让它指向链表的首元结点 LinkList p=L->next。参数 L 其实就是头指针，L->next 就是头结点。然后用工作指针遍历链表，当 p->data 与传入的查找数 e 相等，返回其位置即可。

阅读全文 >>

单链表删除第i个数据结点的算法思路：声明一结点p指向链表第一个结点，初始化j从1开始;当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加 1；若到链表末尾p为空，则说明第i个元素不存在；否则査找成功，将欲删除的结点p->next賦值给q;单链表的删除标准语句p->next=q->next;

阅读全文 >>

昨天我们说了，单链表如何进行初始化操作。初始化之后，我们就创建了一个单链表了，接下来，我们要往这个链表里填充数据，也就是常说的，插入操作。先把结点s的指针next指向ai+1，即 s->next = p->next. 然后再把ai的指针next指向s，即 p->next = s.

阅读全文 >>

初始化一个链表需要做什么事情呢？头指针是必须要有的，头结点为了规范化操作，最好也得有。那么第一步就是：创建一个头结点，并且让头指针指向这个头结点。其实头指针也有了。参数 *L 传入的 L其实就是链表的首地址，也就是头指针。接下来也就是在内存开辟一个区域来作为头结点。

阅读全文 >>

单链表排序是单链表的常见编程任务之一，也是面试中经常出现的题目。单链表排序的关键是交换算法，需要额外考虑。选择排序是比较直观的排序算法之一，这里就使用选择排序实现单链表的排序。如果需要对选择排序复习一下，传送门：算法导论：选择排序的原理与实现。

阅读全文 >>

写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。解决的思路如下：建立指针p，用于遍历链表；建立指针q，q遍历p后面的结点，并与p数值比较；建立指针r，r保存需要删掉的结点，再把需要删掉的结点的前后结点相接。

阅读全文 >>

通过一次遍历找到单链表中倒数第n个节点，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。单向链表的特点是遍历到末尾后不能反向重数N个节点。因此必须在到达尾部的同时找到倒数第N个节点。不管是顺数n个还是倒数n个，其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量，我们能够判断倒数第一个节点，因为他的next==NULL。

阅读全文 >>

给出两个单向链表的头指针，比如h1，h2，判断这两个链表是否相交。（如图，假设两个链表均不带环）最直观的解法就是判断第一个链表中的每个节点是否在第二个链表中。这种方法的时间复杂度是O(Length(h1)*Length(h2))。将两个链表首尾相接，判断相接后的链表是否有环，若有环，则说明两个链表相交。

阅读全文 >>

普通的方法很简单，首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为O(L+L/2)=O(3L/2)。能否再优化一下这个时间复杂度呢？有一个很巧妙的方法：设置两个指针*search、*mid都指向单链表的头节点。其中* search的移动速度是*mid的2倍。当*search指向末尾节点的时候，mid正好就在中间了。这也是标尺的思想。

阅读全文 >>

这是一个比较常见的面试算法题：一次遍历找链表倒数第n个节点。不管是顺数n个还是倒数n个，其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量，我们能够判断倒数第一个节点，因为他的next==NULL。如果我们用两个指针，并保持他们的距离为n，那么当这个线段的右端指向末尾节点时，左端节点就指向倒数第n个节点。

阅读全文 >>

有环的定义是，链表的尾节点指向了链接中间的某个节点。比如下图，如果单链表有环，则在遍历时，在通过6之后，会重新回到3，那么我们可以在遍历时使用两个指针，看两个指针是否相等。方法一：使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。

阅读全文 >>

题目：已知单向链表的头结点head，写一个函数把这个链表逆序 (Intel)。这个题目算是考察数据结构的最基础的题目了，下面我们一步步解析这个算法步骤。首先我们创建一个新结点 current p1，并且让它指向首元结点，即 current p1 = L -> next;然后我们创建另外一个新结点 pnext p2，用来保存当前节点的下一个节点，即 pnext p2 = current p1 -> next;

阅读全文 >>