java实现单链表一些简单算法

妖狐艹你老母 2022-02-05 03:45 199阅读 0赞

单链表实现简单一些算法，在此做一总结：

1. 单链表的反转并输出；

2. 检测一个单链表中是否有环；

3. 将两个有序链表合并；

4. 删除链表中倒数第n个结点；

5. 获得链表中间结点；

代码如下：

public class SingleListNode {
    	private Node head = null;	
    	
    	//插入链表头部；
    	public void insertToHead(int data){
    		Node newNode = new Node(data, null);
    		if(head == null){
    			head = newNode;
    		}else{
    			newNode.next = head;
    			head = newNode;
    		}
    		
    		newNode.next = head;
    		head = newNode;
    	} 	
    	
    	//插入链表尾部；	
    	public void insertToTail(int data){
    		Node newNode = new Node(data, null);
    		if(head == null){
    			head = newNode;
    		}else{
    			Node q = head;
    			while(q.next != null){
    				q = q.next;
    			}
    			newNode.next = q.next;
    			q.next = newNode;
    		}	
    		
    	}
    	
    	//插入链表尾部；	
    		public void insertToTail(Node node){
    			if(head == null){
    				head = node;
    			}else{
    				Node q = head;
    				while(q.next != null){
    					q = q.next;
    				}
    				q.next = node;
    			}	
    			
    		}
    	
    	//单链表的反转并输出；
    	public void reverseList(){
    		if(head == null){
    			return;
    		}			
    		else{			
    			Node pre = null;			
    			while(head.next != null){
    				Node newNode = head.next;
    				head.next = pre;
    				pre = head;
    				head = newNode;			
    			}
    			head.next = pre;
    		}
    		
    	}
    	
    	//检测一个单链表中是否有环；
    	public boolean isLoop(){
    		Node p = head; //low
    		Node q = head; //fast
    		
    		while(q.next != null){
    			q = q.next.next;
    			p = p.next;
    			if(p == q)
    				return true;
    		}
    		
    		return false;
    	}
    	 
    	 //返回指定位置处节点;
    	 public Node findByIndex(int index) {
    	        Node p = head;
    	        int pos = 0;
    	        while (p != null && pos != index) {
    	            p = p.next;
    	            ++pos;
    	        }
    
    	        return p;
    	    }
    	 
    	 //将两个有序链表合并；
    	 @SuppressWarnings("unused")
    	public Node addList(Node a, Node b){
    		 Node head2;
    		 Node p = a;
    		 Node q = b;
    		 if(p.data < q.data){
    			 head2 = p;
    			 p = p.next;
    		 }else{
    			 head2 = q;
    			 q = q.next;
    		 }
    		 Node r = head2;
    		 
    		 while(p != null && q != null){
    			 if(p.data< q.data){
    				 r.next = p;
    				 p = p.next;
    			 }else{
    				 r.next = q;
    				 q = q.next;
    			 }
    			 r = r.next;
    		 }
    		 
    		 if (p != null) {
    		      r.next = p;
    		    } else {
    		      r.next = q;
    		    }
    		 
    		 return head2;
    		 
    	 }
    	 
    	 //删除链表中倒数第n个结点；
    	 public Node deleteNodeFromEnd(int n) throws Exception{
    		 Node r = head;
    		 Node s = head;
    		 Node q = null;
    		 if(r == null)
    			 return null;
    		 int length = 0;
    		 while(r != null){
    			 length++;
    			 r = r.next;
    		 }
    		 System.out.println(length);
    		 if(n > length)
    			 throw new Exception();
    		 if(length == 1 && n == 1)
    			 return q;
    		 if(n == 0)
    			 return s;
    		 
    		 int i = 1;
    		 while(i < length - n){
    			 s = s.next;
    			 i++;
    		 }
    		 s.next = s.next.next;
    		 
    		 return s;
    	 }
    	 
    	 //删除倒数第n个结点代码2（时间复杂度降低）；
    	 public Node deleteNodeFromEnd2(int n) {
    		 Node p = head;
    		 Node q = head;
    		 if(p == null)
    			 return null;
    		 for(int i = 0; i < n; i++){
    			 if(p != null)
    			 p = p.next;
    		 }
    		 
    		 if(p == null)
    			 return q.next;
    		 
    		 while(p.next != null){
    			p = p.next;
    			q = q.next;
    		}
    		 q.next = q.next.next;
    		 return head;
    	 }
    	 
    	 //获得链表中间结点；
    	 public Node getMediaNode(){		 
    		 Node fast = head;
    		 Node slow = head;
    
    		 if(fast == null)
    			 return null;		 
    		 if(fast.next == null)
    			 return head;
    		 if(fast.next.next == null)
    			 return fast.next;
    		 
    		 while(fast.next != null && fast.next.next != null){
    			 fast = fast.next.next;
    			 slow = slow.next;
    		 }
    		 return slow;
    	 }
    
        //打印链表；
    	 public void printAll() {
    	        Node p = head;
    	        while (p != null) {
    	            System.out.print(p.data + " ");
    	            p = p.next;
    	        }
    	        //System.out.println();
    	    }
    	 
    	//打印链表；
    		 public void printAll(Node node) {
    		        Node p = node;
    		        while (p != null) {
    		            System.out.print(p.data + " ");
    		            p = p.next;
    		        }
    		        //System.out.println();
    		    }
    }

链表的算法重点注意使用快慢指针的思想。

以上，小记。