Java 自定义链表并求中间节点

╰+攻爆jí腚メ 2024-02-19 13:38 43阅读 0赞

先定义一个节点类Node

package helper;
    
    //定义一个表示节点的类Node
    public class Node {
    
    	Node next; //下一个节点的引用
    	Object obj; //节点元素
    	
    	
    	public Node(Object obj) {
    		this.obj = obj;
    	}
    
    }

再定义链表类LinkedList

package helper;
    
    //自定义一个链表类LinkedList
    public class LinkedList {
    
    	Node nodeList = null;// 创建一个空链表
    	Node last = nodeList;// 尾节点，并记录当前节点的位置
    	int modCount = 0; // 统计节点个数
    
    	// 添加一个元素
    	public void add(Object obj) {
    		Node node = new Node(obj);
    		modCount++;
    		if (nodeList == null) {
    			nodeList = node; // 如果链表为空，定义头节点
    		} else {
    			last.next = node; // 当前节点的下一个节点
    		}
    		last = node; // 最后的节点为当前节点
    
    	}
    
    	// 删除下标为index的节点
    	public void remove(int index) {
    		if (index >= modCount) {
    			// 抛异常
    			System.out.println("indexOutOfBoundsException!");// 最好自定义异常抛出，这里演示
    			return;
    		}
    		Node node = nodeList;
    		// 如果节点为第一个节点
    		if (index == 0) {
    			nodeList = nodeList.next; // 将头节点指向第二个节点
    			modCount--;
    			return;
    		}
    
    		// 如果节点为最后一个节点,找到最后一个节点的前一个节点,不用管
    		if (index == modCount - 1) {
    			System.out.println("ddd");
    			// 找到最后一个节点的前一个节点
    			int j = 0;
    			while (node != null && j < index - 1) {
    				// 最后一个节点的前一个节点
    				node = node.next;
    				j++;
    			}
    			last = node; // 最后一个节点设置为前一个节点
    			modCount--;
    			return;
    		}
    
    		// 如果节点为中间节点
    		int j = 0;
    		while (node != null && j < index - 1) {
    			// 查找被删除的节点的前一个节点
    			node = node.next;
    			j++;
    		}
    		node.next = node.next.next; // 被删除节点的下一个节点设置为被删除节点的下下个节点
    		modCount--;
    	}
    
    	public int getSize() {
    		return modCount;
    	}
    
    	public Object get(int index) {
    		Node node = nodeList;
    		if (index >= modCount) {
    			// 抛异常
    			System.out.println("indexOutOfBoundsException!");
    			return -1;
    		}
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		return node.obj;
    	}
    
    	// 链表反转
    	public LinkedList reverseList(LinkedList linkedList) {
    		LinkedList temp = new LinkedList();
    		for (int i = linkedList.getSize() - 1; i >= 0; i--) {
    			temp.add(linkedList.get(i));
    		}
    		return temp;
    	}
    
    	// 打印链表-node表示从哪个节点开始打印
    	public void printNode(Node node) {
    		if (node != null) {
    			System.out.print(node.obj+"   ");
    			node = node.next;
    			printNode(node);// 递归调用
    		}
    	}
    	
    	//求中间节点--设置两个指针，一个快指针，每次走两步，一个慢指针，每次走一步
    	public   Node searchMid(Node head) {
    		Node p=head;
    		Node q=head;
    		while(q!=null&&q.next!=null&&q.next.next!=null) {
    			p=p.next;
    			q=q.next.next;
    		}
    		return p;
    	}
    
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		LinkedList ls =new LinkedList();
    		ls.add(1);
    		ls.add(3);
    		ls.add(5);
    		ls.add(7);
    		
    		System.out.println("打印链表");
    		ls.printNode(ls.nodeList);
    		System.out.println();
    		
    		System.out.println("删除元素");
    		ls.remove(1);
    		ls.printNode(ls.nodeList);
    		System.out.println();
    		
    		System.out.println("链表中的最后一个元素");
    		System.out.println(ls.last.obj);
    		
    		System.out.println("链表中索引为1的元素");
    		System.out.println(ls.get(1));
    		
    		System.out.println("链表反转");
    		LinkedList n =ls.reverseList(ls);
    		n.printNode(n.nodeList);
    		System.out.println();
    		
    		System.out.println("获取链表中间节点");
    		Node p=ls.searchMid(ls.nodeList);
    		System.out.println(p.obj);
    		
    		System.out.println("获取链表大小");
    		System.out.println(ls.modCount);
    
    	}
    
    }

打印链表  
1 3 5 7  
删除元素  
1 5 7  
链表中的最后一个元素  
7  
链表中索引为1的元素  
5  
链表反转  
7 5 1  
获取链表中间节点  
5  
获取链表大小  
3