数据结构链表实现

package SqList_Operator;

import java.text.MessageFormat;

public class LinkListTool {
	public LinkListTool(){
		
	}
	
	public int getListLength(LinkList l){
		
		int k=1;
		LNode tempNode = l.getStartNode();
		while(tempNode.getNext()!=null){
			tempNode = tempNode.getNext();
			k++;
			
		}
		return k;
		
	}
	//在链表中查找指定的元素
	public LNode getNode(LinkList l,int e){
		
		LNode resultNode = null;
		LNode tempNode = l.getStartNode();
		while(tempNode!=null){
			if(tempNode.getData()==e){
			
			    resultNode = tempNode;
			    break;
				}
			else {
				tempNode = tempNode.getNext();
			}
			
		}
		
		return resultNode;
		
	}
	public void listInsert(LinkList l,LNode p,LNode s)
	{
		//在p结点之前插入结点s
		if(p==l.getStartNode()){
			s.setNext(p);
			l.setStartNode(s);
			
			
		}
		else{
			LNode temp = l.getStartNode();
			while(temp.getNext()!=p&&temp!=null){
				temp = temp.getNext();
				
			}
			if(temp!=null){
				System.out.print("链表中不存在");
				
			}
			else{
				temp.setNext(s);
				s.setNext(p);
			}
		}
		
	}
	//逆置单链表
	public void invertLinkedList(LinkList l){
		
		System.out.print("逆置单链表之前的结点为：");
		printLinkList(l);
		
		LNode p = l.getStartNode();
		LNode r = p.getNext();
		LNode s =null;
		p.setNext(null);
		/*l.setStartNode(null);*/
		while(r!=null){
			s = r.getNext();
		    r.setNext(p);
		    p=r;
			l.setStartNode(r);
			r = s;
			/*System.out.print("test");*/
			
		}
		System.out.print("逆置单链表之后的结点为：");
		printLinkList(l);
		/*while(p!=null){
			LNode r = p.getNext();
			p.setNext(l.getStartNode());
			l.setStartNode(p);
			p = r;
			
		}*/
		
	}
	//将链表lb中所有在la链表中不存在的点插入到la链表中,并释放lb中多余的点
	public void union_L(LinkList la,LinkList lb){
		
		System.out.print(MessageFormat.format("源链表{0}为:",la ));
		printLinkList(la);
		if(la==null){
			la = lb;
			
		}else{
			//否则遍历lb中的结点
			
			LNode q = lb.getStartNode();
			LNode pre = null;
			while(q!=null){
			/*	LNode p = lb.getStartNode();*/
				LNode s = q;
				q = q.getNext();
				LNode r = la.getStartNode();
				while(r!=null&&s.getData()!=r.getData()){
					//将lb中的结点加入到la中
					 pre = r;
					r = r.getNext();
					
				}
				if(r!=null){
					//找到了相同的元素，则删除
					
					
				}
				else{
					pre.setNext(s);
					s.setNext(null);
				}
			}
			
		}
		System.out.print(MessageFormat.format("源链表{0}为:",la ));
		printLinkList(la);
	}
	
	//对带有头结点的单链表进行排序,利用直接插入对链表进行排序
	public void linkListInsertSort(LinkList l){
		//直接插入默认链表的第一个结点是有序的，直接插入则从链表的第二个结点开始
		System.out.print("排序之前源链表为：");
		printLinkList(l);
		if(l.getStartNode()!=null){
			
			LNode node = l.getStartNode().getNext();
			l.getStartNode().setNext(null);
			while(node!=null){
				LNode q = node.getNext();
				LNode p = l.getStartNode();
				LNode pre = null;
				while(p.getData()<node.getData()&&p!=null){
					pre = p;
					p = p.getNext();
					
				}
				if(pre==null){
					//说明第一个结点就比待插入的大
				   node.setNext(p);
				   l.setStartNode(node);
					
				}else{
					pre.setNext(node);
					node.setNext(p);
				}
				node = q;
				
				
				
			}
			
		}
		
		System.out.print("排序之后源链表为：");
		printLinkList(l);
		
	}
	//求解两个有序链表的交集
	public LinkList unionList(LinkList la,LinkList lb){
		LinkList lc = new LinkList();
		lc.setStartNode(null);
		LNode pa = la.getStartNode();
		LNode pb = lb.getStartNode();
		//遍历两个链表，找到两个链表中相同的元素
		while(pa!=null&&pb!=null){
			if(pa.getData()<pb.getData()) pa = pa.getNext();
			else if(pa.getData()>pb.getData()){
				
				pb = pb.getNext();
			}
			else{
				//pa.getData=pb.getData的情况，就将该结点插入到链表lc中去
				LNode tempNode = new LNode(pa.getData());
				tempNode.setNext(lc.getStartNode());
				lc.setStartNode(tempNode);
				pa = pa.getNext();
				pb = pb.getNext();
				//pa就成了lc链表中的第一个结点
				
				
				
			}
			
		}
		return lc;
		
	}
	//删除链表中的最小值结点
	public void deleteMinNode(LinkList l){
		System.out.print("删除之前源链表为：");
		printLinkList(l);
		LNode pre = l.getStartNode();
		LNode node = l.getStartNode();
		LNode min = null;
		
		//用pre来记录最小值结点的前驱
	    while(node.getNext()!=null){
	    	if(node.getData()>node.getNext().getData()){
	    		pre = node;
	    		min = node.getNext();
	    		
	    	}
	    	node = node.getNext();
	    	
	    }
	    System.out.print(pre.getData());
	    System.out.print(min.getData());
	    /*if(pre.equals(l.getStartNode())){
	    	l.setStartNode(pre.getNext());
	    	
	    }*///这种情况应该如何处理
	    pre.setNext(min.getNext());
	    min.finalize();//释放最小值结点
	    System.out.print("删除之后源链表为：");
		printLinkList(l);
		
		
	}
	//将两个有序链表合并，并且合并后的链表仍然是有序的
	public LinkList unionListTwo(LinkList la,LinkList lb){
		System.out.print("合并之前源链表为：");
		printLinkList(la);
		LNode pa = la.getStartNode();
		LNode pb = lb.getStartNode();
		LNode pre = null;
		LNode pos = null;
		//这里以链表la做为基础
		while(pa!=null&&pb!=null){
			
			if(pa.getData()<=pb.getData()){
				pre = pa;
				pa = pa.getNext();
				
			}
			else if(pa.getData()>pb.getData()){
				//其实我这里可以生成结点，不破坏lb原本的结构的
				pre.setNext(pb);
				if(pre==null)//我想用equal()方法来判断pre和pa指的是不是同一个结点
				{
					pb.setNext(pa.getNext());
					}
				else{
					
					pos = pb.getNext();//我这里还不能释放pb，如果我需要释放的话，我应该new一个结点和
					//和pb的data相同，再释放
					pb.setNext(pa);
				}
				pb = pos;
				
				
			}
			
			
		}
		//如果循环结束后，pa已经为空，单pb不为空，则要遍历pb中的结点，依次放入到pb中
		//但是如果pb为空，pa部位空，则将pa的剩下的链接过去
		if(pa!=null){
			pre.setNext(pa);
			
		}else{
			while(pb!=null){
				pre.setNext(pb);
				pre = pb;
				pb = pb.getNext();
			}
			
		}
		System.out.print("合并之后源链表为：");
		printLinkList(la);
		return la;
		
	}
	//两个链表的差集，即对链表la删除la和lb共同有的结点
	public void differenceList(LinkList la,LinkList lb){
		System.out.print("删除公共结点之前源链表为：");
		printLinkList(la);
		LNode pa = la.getStartNode();
		LNode pb = lb.getStartNode();
		LNode pre = null;
		LNode pos = null;
		while(pa!=null&&pb!=null){
			if(pa.getData()<pb.getData()){
				pre = pa;
				pa = pa.getNext();//因为涉及到删除因此需要把记录前驱
			}else if(pa.getData()>pb.getData()){
				pb = pb.getNext();
				
			}else{
				//这就说pa.getData==pb.getData();
				/*pre.setNext(pb);
				pos = pb.getNext();
				pb.setNext(pa);
				pa = pa.getNext();
				pb = pos;
				*/
				//删除
				pre.setNext(pa.getNext());
				pos = pa;
				pa = pa.getNext();
				pos.finalize();//释放该结点
				
			}
			
		}
		
		System.out.print("删除公共节点之后源链表为：");
		printLinkList(la);
		
	}
	public void addLinkNode(LinkList l,LNode node){
		//向链表l中加入结点
		//首先应该经过遍历到达链表的尾端
		LNode start = l.getStartNode();
		LNode temp = start;
		while(temp.getNext()!=null){
			temp = temp.getNext();
			
		}
		//遍历完成后temp则为待插入结点的前驱结点
		//但是如果链表中只存在这头结点，那么temp本身就是空的
		if(temp!=null){
			temp.setNext(node);
			node.setNext(null);
		}else{
			l.setStartNode(node);
			node.setNext(null);
		}
		
	}
	//还有一个功能应该是打印链表
	public void printLinkList(LinkList l){
		LNode startNode = l.getStartNode();
		LNode temp = startNode;
		if(temp==null){
			System.out.print("该链表为空链表");
			
		}
		while(temp!=null){
			System.out.print("结点数据为："+temp.getData());
			temp = temp.getNext();
			System.out.println();
			
		}
		
	}
	
	
	
	
	

}

package SqList_Operator;

public class LinkList {
	
	private	LNode startNode;
	private int length;
	public LinkList(LNode startNode){
		this.startNode = startNode;
		startNode.setNext(null);
		
		
	}
	public LinkList(LinkList l){
		this.startNode = l.getStartNode();
		
	}
	public LinkList(){}
	public LNode getStartNode() {
		return startNode;
	}
	public void setStartNode(LNode startNode) {
		this.startNode = startNode;
	}
	public int getLength() {
		return length;
	}
	public void setLength(int length) {
		this.length = length;
	}

}