玩转单链表

       学会了单链表的基本操作之后，我们就可以自定义一些非常有意思的功能了，例如对单链表中的元素进行排序，（排序规则可以由自己定），将链表翻转等等，这里主要是讲老师布置的几个问题，我觉得也非常有趣，大家也可以思考一下，由于这些方法几天前就写完了，五一假在家中也没有对之前的链表进行更多的修改了，所以还是用之前所写过的单链表结构继续添加功能吧。

       在实现所有功能之前先来个前言，接下来的这两个方法对后面的每一步都是至关重要的，第一个是获取链表长度的方法：

获取链表长度的方法其实可以是打印链表方法的翻版，我最开始的时候也是这样做的，不过后来发现了一个更好的更不容易出错的方法，在链表类中定义一个size属性

      int size=0;

    然后在所有的对链表有长度修改的方法中都对size进行一次修改，例如添加元素的方法最后加一句size++,删除元素的方法最后加一句size--等等（当然size不能小于0）。

    这样获取size的方法中只需要一句话就可以解决了：

int size(){

           return size;

  }

另外一个就是获取指定位置结点元素的方法，如下：

/**
* 查找指定位置结点元素的方法
  */
public Node get(int index){
	Node node=head;
	int j=1;
	//找到第index
	while(node!=null&&j<index){
		node=node.next;
		j++;
	}
	return node;
}

 

下面在具体问题中来看一下这两个方法的应用吧。

                 1.对链表中的元素进行排序（如果链表中的元素是整数的话）

相信看完前两个方法之后，排序的方法已然在心中出现了，如果这不是一个单链表而是一个数组的话，对数组进行排序相信大家都不会陌生了，所以这里也只是用到了最简单的冒泡排序思想而已：

 

/**
 * 如果链表中的元素是整型元素，则排列链表
*/
public void sort(){
	Object obj=null;
	Node temp=new Node(obj);//媒介结点
	for(int i=0;i<=size();i++){
		for(int j=i+1;j<=size();j++){
			//冒泡排序思想,交换数据域
			if(Integer.parseInt((String)get(i).obj)>Integer.parseInt((String)get(j).obj)){
				temp.obj=get(i).obj;
				get(i).obj=get(j).obj;
				get(j).obj=temp.obj;
			}
		}
	}
}

2．将链表中的元素封装到一个数组当中

看到这里大家可能会觉得奇怪，为什么这个方法不写在上面，第一个方法不就是利用了这个思想么？其实只是因为我是在做完第一个题目之后才想到的这个方法，所以放在之后讲，我想这正跟我们的学习过程一样，很多简单的方法是在做了复杂的方法之后才想出来的：

 

/**
 * 将链表封装成一个对象数组
*/
public Object[] toArray(){
	//创建
	Object obj[]=new Object[size()];
	Node node=head;
	int j=0;
	while(node!=null&&j<obj.length){
		obj[j++]=node.obj;
		node=node.next;
	}
	return obj;
}

 

3. 将链表翻转

最开始看到这个题目的时候，我还在反复推敲，如何把链表的引用域与数据域对调过来，因为这样就可以实现链表的翻转的工作，在那折腾了半个小时之后才发现，是我2B了，要实现链表翻转其实就像链表排序一样，只要交换数据域就行了，方法如下：

 

/**
 * 翻转链表的方法
 */
public void turn(){
	int j=size(); //获取最后一个下标位置
	//将前一半与后一半的位置交换
	Object temp;
	for(int i=1;i<=size()/2;i++){
		temp=get(i).obj;
		get(i).obj=get(j).obj;
		get(j).obj=temp;
		j--;
	}
}

       4．如果该单链表具有环，怎么样找到环的入口位置？

这里采用的是穷尽搜索的方法，当然你还可以用效率更高的二分搜索法，不过我想不管是哪个方法，在搜索之前先判断要不要搜索都比搜索本身来的快一点，如何判断一个链表是否有环呢？很简单，当last结点的next域为空时链表不就没有环了么，方法如下：

      

/**
 * 搜索环链表环的位置的入口
*/
public void searchHoop(){
	Node node=head;
	int location=1; //环的入口位置
	while(node!=null&&location<=size()){
		node=node.next;//寻找下一个结点
		if(last.next==null){
			System.out.println("该链表没有环");
			break;
		}
		//如果最后一个结点的引用指向了之中的某一个结点
		else if(last.next==node&&location<=size()){
			System.out.println("环的入口位置为第"+location+"个结点");
			break;
		}
		location++;
	}
}

方法实现方面就先讲到这了，不过由于之前的发的那篇关于单向链表的实现上，语法结构其实并不严谨，后面几个方法在使用起来可能需要稍做揣摩，此外，也希望大家一起来探讨一下更多有趣的方法。