myJavaBlog

java世界
随笔 - 43, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

单链表，你懂了吗？

首先，上一道开胃菜：怎么判断两个单链表是否相交？ 
      我们假设两个单链表分别是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）即可。第一个相同的元素即为所求。参看下图可以帮助理解： 



      实现代码如下： 
Java代码  收藏代码
  1. /** 
  2.      * 寻找两个单链表第一个相同的元素。 
  3.      * @param A 第一个单链表 
  4.      * @param B 第二个单链表 
  5.      * @return 若存在相同元素，则返回其值；否则返回-1并打印消息 
  6.      */  
  7.     public static int findSame(FLinkedList A, FLinkedList B){  
  8.         int m = A.length();  
  9.         int n = B.length();  
  10.         FLinkedNode aHead = A.getElem(0);  
  11.         FLinkedNode bHead = B.getElem(0);  
  12.         if(m >= n){  
  13.             int s = m - n;  
  14.             for(int i = 0; i < s; i ++){  
  15.                 aHead = aHead.getNext();  
  16.             } // end for  
  17.             while(aHead.getNext() != null){  
  18.                 if(aHead.getValue() == bHead.getValue()){  
  19.                     return aHead.getValue();  
  20.                 }else{  
  21.                     aHead = aHead.getNext();  
  22.                     bHead = bHead.getNext();  
  23.                 } // end if-else  
  24.             } // end while  
  25.         }else{  
  26.             int s = n - m;  
  27.             for(int i = 0; i < s; i ++){  
  28.                 bHead = bHead.getNext();  
  29.             } // end for  
  30.             while(aHead.getNext() != null){  
  31.                 if(aHead.getValue() == bHead.getValue()){  
  32.                     return bHead.getValue();  
  33.                 }else{  
  34.                     aHead = aHead.getNext();  
  35.                     bHead = bHead.getNext();  
  36.                 } // end if-else  
  37.             } // end while  
  38.         } // end if-else  
  39.         System.out.println("没有找到相同的元素！！");  
  40.         return -1;  
  41.     } // 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：这些问题肯定还有更好地解法和方案，希望您不吝赐教。 
（转载请注明出处：[url=http://www.k6567.com]e世博[/url]
[url=http://www.d9732.com]澳门博彩[/url]）

posted on 2012-04-18 15:28 夏凡 阅读(214) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航: