【数据结构】链表(2)

JAVA中，容器库提供了java.util.LinkedList这一个泛型链表容器， 其本质是一个双向链表。与此功能类似的还有一个java.util.ArrayList容器，虽然它不是一个链表容器，但却是一个与链表功能类似的线性表容器，它使用拼接数组的方式实现了容量的灵活变化。由于其容器本质是一个数组，因此访问效率高于链表。然而由于其扩充数组容量是通过新建一个更大数组并复制原有数据的过程来实现，所以这个操作略显耗时。总的来说，两种容器各有优劣，代码的实现也很具有学习价值。

了解java.util.LinkedList和java.util.ArrayList的源码可以参考我的文章《【源代码】java.util.LinkedList》，《【源代码】java.util.ArrayList》。

面试常见问题

我前边说过，链表是面试时考官的大爱，那么这里总结一些面试常见链表问题供大家参考和讨论。

1. 仅给定一个单项链表中间的某一节点索引（或地址），在不知道头指针的情况下删除这个节点。

这个问题很常见。我们知道单链表中当前节点有且仅有后继（下一节点）的地址，在不知道头节点地址的情况下，无法获取某一节点的前驱。所以考虑如下情况，我们可以考虑删除指定节点的后继，在删除之前复制后继的值到当前节点即可。

2. 如何检查一个单向链表中是否有环（某一节点的后继为某一前驱）。

可以考虑两个指针遍历链表，一个指针步进为1，另一指针步进为2，也就是一个一次遍历1个next索引，另一个一次遍历2个next索引。如果某一时刻两个指针相遇则代表有环，如果某一指针发现链表结尾则该链表没有环。

3. 给定两个单向链表头指针，确定两个链表是否相交。

要知道单向链表一旦相交，则交点之后的链表为两者共享。那么我们可以定义两个指针，同时遍历两根链表，每次循环两个指针同时向后移动一个索引，当索引到的对象为统一对象时则发现交点。那么如何保证两个指针能够同时到达交点呢？可以使长度较短的链表由头结点开始，长度较长的由索引为（长链表长度 - 短链表长度）的节点开始同时移动即可。

4. 给定一个单项链表的头指针，就地翻转每一个节点的索引方向，即首尾倒置。

这里提供一个解决方案。建立三个索引，分别代表当前节点，前驱和后继，每次循环改变当前节点的next索引到前驱，并逐一将三个索引后移一位，最后完成链表倒置操作。其中有不少陷阱需要处理。一下是我的代码，可以加在之前自定义的LinkedList类中作为成员方法。

public void reverse(){
		if(head != null || head.next != null){
			Node previous = null;
			Node current = head;
			Node next = current.next;
			
			while(next != null){
				current.next = previous;
				previous = current;
				current = next;
				next = next.next;
			}
			current.next = previous;
			head = current;
		}
	}

5. 复制一个复杂单链表（节点中包含不止一个索引，并且索引无序）。

下图是一个复杂单链表示意图。这里假设节点中包含三个成员变量，值、后继引用和其他节点引用。

这里提供我的一个解决方案。逐一遍历每个节点，复制单链表的主干，其他节点引用先空置。同时用一个哈希表以<当前序号，引用序号>的形式将当前节点的序号和其对应的其他节点序号存储起来。这个听起来有点复杂，以上图为例，节点4的其他节点指向节点1，所以这个key-value-pair就为4->1。

开始复制时也是先复制主干，逐一得到一个新的单链表。然后根据刚才的哈希表可以得到当前新节点应该指向的索引值。

（编辑：ASP站长网）