你真的懂单链表吗

      首先，上一道开胃菜：怎么判断两个单链表是否相交？
      我们假设两个单链表分别是A（有m个结点）和B（有n个结点），当然，最容易想到的肯定是两层循环，遍历A中的元素，然后分别与B中的元素进行比较，但是这样做的时间复杂度达到了O(m*n)，那么有没有更简单的办法呢？肯定有！
      我们来看看单链表的性质：每个结点只通过一个指针指向后继结点。那么是不是意味着两个单链表如若相交，它们就只能是Y形相交，而不可能是X形相交，亦即从第一个相同的结点开始，后面的结点全部一样。如果能想到这个，后面的就简单明了了：只要A链表和B链表的最后一个结点值相等，则证明A链表和B链表相交。该算法的时间复杂度也下降到O(m+n)。
      我们进一步来思考：怎么找到第一个相交的元素呢？
      这里就当然不能像刚才那样，但是出发点还是一样，我们同样可以保证只要两次遍历。我们假设m > n，那么如果我们将两个链表的末尾对齐，是不是从最后一个往前看（当然单链表不能往前遍历，我们先这样看）的时候，A链表会比B链表多m-n个元素，而A链表中的前m-n个元素可以忽略，直接从第m-n个元素开始和B链表一起向前遍历，比较A链表上第m-n+i个元素和B链表第i个元素（i<n）即可。第一个相同的元素即为所求。参看下图可以帮助理解：

      实现代码如下：

/**
	 * 寻找两个单链表第一个相同的元素。
	 * @param A 第一个单链表
	 * @param B 第二个单链表
	 * @return 若存在相同元素，则返回其值；否则返回-1并打印消息
	 */
	public static int findSame(FLinkedList A, FLinkedList B){
		int m = A.length();
		int n = B.length();
		FLinkedNode aHead = A.getElem(0);
		FLinkedNode bHead = B.getElem(0);
		if(m >= n){
			int s = m - n;
			for(int i = 0; i < s; i ++){
				aHead = aHead.getNext();
			} // end for
			while(aHead.getNext() != null){
				if(aHead.getValue() == bHead.getValue()){
					return aHead.getValue();
				}else{
					aHead = aHead.getNext();
					bHead = bHead.getNext();
				} // end if-else
			} // end while
		}else{
			int s = n - m;
			for(int i = 0; i < s; i ++){
				bHead = bHead.getNext();
			} // end for
			while(aHead.getNext() != null){
				if(aHead.getValue() == bHead.getValue()){
					return bHead.getValue();
				}else{
					aHead = aHead.getNext();
					bHead = bHead.getNext();
				} // end if-else
			} // end while
		} // end if-else
		System.out.println("没有找到相同的元素！！");
		return -1;
	} // end findSame

（代码中的FlinkedList是本人自己实现的单链表，功能和系统的LinkedList差不多，方法的功能大家看名字就基本知道了，只是它是更纯粹的单链表而已）

      下面来看看其它的几个单链表相关的典型问题（贴代码太占空间，这里就只谈谈思路，大家可以动手试试）：

      单链表的反转
      如题，怎么实现一个单链表A（有m个元素）的反转呢？
      方案一：如果不能破坏原单链表，我们需要重新新建一个链表C，然后遍历原来的A链表，对C链表实行头插法建表（头插法即将新加入的结点作为链表的头结点，对应的还有尾插法，即直接在链表末尾添加元素）；
      方案二：如果可以破坏原单链表呢？暴力一点的办法是不断地交换相邻的两个元素，即首先将第一个元素通过m-1次交换使其变成链表的最后一个元素，然后又是同样的方法将现任的第一个元素通过m-2次交换使其成为链表的倒数第二个元素，以此类推。

      单链表的排序
      就排序原理而言，个人觉得其实不用过多考虑存储结构的问题，即不管是顺序存储还是链式存储，都不影响排序的基本原理，只是不同的存储结构会影响不同排序方法的效率而已。因为我们完全可以夸张地将顺序存储也想象为不连续的存储只是它们相邻两者的间隙极端的小。即我们将货物分别存在美国和中国的仓库里和都存放在一个仓库里是一样的，只是运费问题而已。
      明白了这一点，那么单链表的排序就和普通的数组排序没有什么太大的区别。我们现在要做的事就是针对性地选择一个时间性能相对较好的排序算法。
      我们知道的排序方法有很多：插入排序、冒泡排序、快速排序、归并排序、堆排序以及基数排序等等，那么这其中哪些对顺序结构和链式结构不那么感冒呢？熟悉这些排序的童鞋肯定知道，是插入排序和冒泡排序。其他的几种常见排序方法就比较偏袒顺序存储结构了。所以，如果要对链表进行排序，我会选择插入排序或者冒泡排序。（不太清楚这些基本排序原理的click here：http://wlh0706-163-com.iteye.com/blog/1465570）

      删除单链表中的最小元素
      我能想到的办法就是遍历两次：第一次找到单链表中最小的元素，第二次遍历删除该元素。第一次遍历的时候需要借助两个变量，一个保存当前的最小元素的值，另一个保存当前最小值的位序。第二次遍历的时候当然就是删除第一次遍历得到的最小元素的位序上的元素了。

      删除所有重复结点
      这个一般得借助其他的数据结构了。基本思路应该是：遍历链表，用一个数据结构保存当前已经遍历的元素，若下一个访问的链表里的元素已经存在于已经访问的元素集合中，则删除单链表中的该元素，否则继续，直至到达链表的末尾。保存已经访问过的元素可以用数组，也可以用其他的。

      判断一个链表是否包含另一个链表
      这个问题其实和开篇的问题一样，只是换了一种说法而已。因此只要找到第一个相同的元素就可以了。

      找出单链表中的倒数第K个元素
      我们首先要确保的就是单链表的元素个数大于K。
      这里的实现思路也很巧妙：我们定义两个指针a和b，全部指向链表的头结点，然后a指针开始向后遍历，但a遍历到第K个元素的时候，b指针也开始从头开始遍历，接下来的事你应该知道了，当a指针到达链表的末尾时，b指针恰好指着链表的倒数第K个元素。这样的时间复杂度是O(n)。

      推广一下：怎么找单链表中间的那个元素呢？Ok, u let me know!

      PS：这些问题肯定还有更好地解法和方案，希望您不吝赐教。

评论

14 楼 luliangy 2012-05-09  

哥哥，单链表反转好像原地逆置考的比较多一些。

13 楼 暗夜魅影 2012-04-22  

表示你怎么不把单链表就地逆置补充上啊

12 楼 风子柒 2012-04-18  

a49688448 写道

Y型相交，不是X型相交，历害！

哈哈，这个怎么厉害了 

11 楼 风子柒 2012-04-18  

mfkvfn 写道

关于《找出单链表中的倒数第K个元素》，我认为:
倒数第K个元素   = 正数第(size-K+1)个
只要知道了size就很简单了。

如果List是用数组实现的(比如Java语言中)，得到size只需要O(1)的时间，则找出单链表中的倒数第K个元素时间复杂度为O(1+K)。
如果List不是用数组实现的，时间复杂度为O(n+K)，跟你说的方法要模一样，我这种算法显然比你的要简单很多，而且也容易理解。

还是觉得不能单在Java语言范畴讨论单链表，Java中的List可以当做很多数据结构来使用，比如双向链表。当然，如果是用数组实现肯定是这种方法好了，推广到链式存储结构，觉得肯定就得这样有效率些了。

10 楼 风子柒 2012-04-18  

mfkvfn 写道

另外《删除单链表中的最小元素》这个，在Java中LinkedList的remove(Object element)时间复杂度是O(1)，因为Java中LinkedList用的是双向链表，所以只需要改变前后节点的指针就行了，核心代码是
e.previous.next = e.next;
e.next.previous = e.previous;

我觉得在考虑数据结构时，要跳出编程语言的范畴，因为语言只是一种工具，单就单链表来看，我觉得这是一个比较可行的方法。

9 楼 风子柒 2012-04-18  

mfkvfn 写道

另外《单链表的反转》你那2种方法都不好，有一种叫“单链表就地逆置”的常见问题。
不需要新的链表，只需要申请一个指针，而且时间复杂度是O(n)。
你自己搜索一下“单链表就地逆置”网上有很多。

嗯，谢谢了，呵呵，这个当时没有思考太多，丢脸了，哈哈。再次表示感谢

8 楼 风子柒 2012-04-18  

mfkvfn 写道

2-->3-->5-->7-->11和5-->10-->15都出现了5算不算相交？

单链表本身就指定了每个结点只通过一个指针指向后继结点。也就杜绝了这种现象的发生了。

7 楼 a49688448 2012-04-18  

Y型相交，不是X型相交，历害！

6 楼 mfkvfn 2012-04-18  

关于《找出单链表中的倒数第K个元素》，我认为:
倒数第K个元素   = 正数第(size-K+1)个
只要知道了size就很简单了。

如果List是用数组实现的(比如Java语言中)，得到size只需要O(1)的时间，则找出单链表中的倒数第K个元素时间复杂度为O(1+K)。
如果List不是用数组实现的，时间复杂度为O(n+K)，跟你说的方法要模一样，我这种算法显然比你的要简单很多，而且也容易理解。

5 楼 mfkvfn 2012-04-18  

另外《删除单链表中的最小元素》这个，在Java中LinkedList的remove(Object element)时间复杂度是O(1)，因为Java中LinkedList用的是双向链表，所以只需要改变前后节点的指针就行了，核心代码是
e.previous.next = e.next;
e.next.previous = e.previous;

4 楼 mfkvfn 2012-04-18  

另外《单链表的反转》你那2种方法都不好，有一种叫“单链表就地逆置”的常见问题。
不需要新的链表，只需要申请一个指针，而且时间复杂度是O(n)。
你自己搜索一下“单链表就地逆置”网上有很多。

3 楼 mfkvfn 2012-04-18  

2-->3-->5-->7-->11和5-->10-->15都出现了5算不算相交？

2 楼 风子柒 2012-04-18  

JuliaAilse 写道

呀！表示主页名跟我的好像啊！

额，看不出来哪里像了

1 楼 JuliaAilse 2012-04-17  

呀！表示主页名跟我的好像啊！