Java链表

灰太狼 2022-05-29 14:16 159阅读 0赞

package myTest;
    public class Node{
    	int data=-1;
    	Node next;	
    	Node(int data){
    		this.data=data;
    		
    	}
    	Node(){
    		
    	}
    	public static Node BuildmyLinkarr(int []arr,boolean HasHeadNode){
    		if (arr.length<=0){return null;}
    		if(HasHeadNode){
    			Node Head =new Node();//头结点
    			Node p=Head;//pre存储第一个有效结点的地址
    			for(int i=0;i<arr.length;i++){
    				p.next=new Node(arr[i]);//建立新节点，并将该节点的地址存储到上一个结点的next中
    				p=p.next;//将上一个结点的指针向后移动一个结点
    			}
    			p.next=null;
    			return Head;
    		}
    		else {
    			Node Head=new Node(arr[0]);//p存储第一个有效结点的地址
    			Node p=Head;
    			for(int i=1;i<arr.length;i++){
    				p.next=new Node(arr[i]);//建立新节点，并将该节点的地址存储到上一个结点的next中
    				p=p.next;//将上一个结点的指针向后移动一个结点
    				
    			}
    			p.next=null;
    			return Head;
    			
    		}
    	}
    	public static void PrintLinkarr(Node Head,boolean HasHeadNode){
    		if(HasHeadNode){
    		Node p=Head.next;
    		System.out.println("Now it is printing:");
    		while(p!=null){
    			System.out.println(p.data);
    			p=p.next;
    		}
    		}
    		else {
    		Node p=Head;
    		System.out.println("Now it is printing:");
    		while(p!=null){
    			System.out.println(p.data);
    			p=p.next;
    		}
    			
    		}
    	}
    	public static Node Reverse(Node Head,boolean HasHeadNode){
    		if(HasHeadNode){
    			Node p1=Head.next;
    			Node p2=p1.next;
    			while(p2!=null){
    				Node p3=p2.next;
    				p2.next=p1;
    				p1=p2;
    				p2=p3;
    			}
    			Head.next.next=null;
    			Head.next=p1;
    			return Head;
    		}
    		else {
    			Node p1=Head;
    			Node p2=p1.next;
    			while(p2!=null){
    				Node p3=p2.next;
    				p2.next=p1;
    				p1=p2;
    				p2=p3;
    			}
    			Head.next=null;
    			Head=p1;
    			return Head;
    			
    		}
    	}
    	public static void main(String []args){
    		int[]arr=new int[]{4,3,5,6,2};
    		System.out.println("Have HeadNode:(有头结点)");
    		Node myHead=BuildmyLinkarr(arr,true);
    		PrintLinkarr(myHead,true);
    		myHead=Reverse(myHead,true);
    		PrintLinkarr(myHead,true);
    		System.out.println("No HeadNode:(没有头结点)");
    		Node myHead2=BuildmyLinkarr(arr,false);
    		PrintLinkarr(myHead2,false);
    		myHead2=Reverse(myHead2,false);
    		PrintLinkarr(myHead2,false);
    		
    	}
    }

这部分代码已经测过，可以直接运行，保存在Node.java中。

具体来说，我用java实现了几个功能：建立链表，翻转链表和输出链表。这里的链表分为两种（带头结点的单链表和不带头节点的单链表）

注意：需要注意的是，带头结点的单链表还是有好处的，不用担心头指针改变。（函数返不返回头指针都可以，因为头指针Head不改变）

而不带头结点的链表在执行完Reverse(Head,false)这个函数之后头指针指向的地址会发生改变，因此该操作一定要返回头指针。

此外，单链表的翻转我也终于弄懂了：

对于含有头结点的链表和不含头结点的链表，要做的是先画图，画了流程之后自然就不会错了：

Node p1=Head.next;
    			Node p2=p1.next;
    			while(p2!=null){
    				Node p3=p2.next;
    				p2.next=p1;
    				p1=p2;
    				p2=p3;
    			}
    			Head.next.next=null;
    			Head.next=p1;
    			return Head;

上面这部分对应的思路如下：

a.需要定义三个额外的指针（引用变量p1,p2,p2，这三个指针一开始分别指向第1,2,3个结点）

b.然后第二个结点指向第一个结点

c.p1,p2,p3分别向后滑动一位。

d.重复b操作

直到p2指向null，停止循环

e.将第1个结点指向null

d.将头结点指向原来的尾结点（结点4）

![70][]

[70]: /images/20220529/5afe57208f2f4c978fac640a7ea95048.png