Java-单链表相关总结

链表基类

/***
*@author: Q.sir
*@date:2021-06-08
*@desc:仅限本类操作，有些方法未加兼容及拓展
*/
class Node {
	Node next;
	int data;
	public Node(int data) {
		this.data = data;
	}
}

链表相关操作， 增删改查 排序， 去重，链表反转 等, 以linkeLIst,数据类型为int为例， 若兼容其他适用泛型做兼容。

class LinkeList {
	Node head = null;
	
	/**
	** 添加新的数据
	*@data 
	**/
	public add(int data) {
		Node newNode = new Node(data);
		if(head == null) {
			head = newNode;
			return;//结束该判断，向下执行。
		}
		Node temp = head;
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}

	public boolean deleate(int index) {
		if(index < 0 || index > length()) return true;
		if(index == 0) {
			head = head.next;
			return true;
		}
		int i;
		Node preNode = head;
		Node curNode = preNode.next;
		while(curNode.next != null) {
			if(i == index) {
				curNode = curNode.next;
				return true;
			}
			curNode
		}
		return true;
	}

	public Node sort() {
		Node currNode = head;
		while(currNode != null) {
			Node nextNode = currNode.next;
			while(nextNode != null) {
				if(currNode.data > nextNode.data) {
					int temp = currNode.data;
					currNode.data = nextNode.data;
					nextNode.data = temp;
				}
				nextNode =nextNode.next;
			}
			currNode = currNode.next;
		}
	
	}
	
	public void print() {
		Node currNode = head;
		while(currNode != null) {
			System.out.print(currNode.data + "\n");
			currNode = currNode.next;
		}
	}
	
	/**
	*去除重复元素
	*@return返回重复数据
	**/
	public Node distinct() {
		Node temp = head;
		Node pre = null;
		HashTable<Integer, Integer> ht = new HashTable<>();
		while(temp != null) {
			if(ht.containKey(temp.data)) {
				pre.next = temp.next;
			} else {
				ht.put(temp,data, 1);
				pre = temp;
			}
			temp = temp.next;
		}
		return pre;
	}

	/**
	*查找index 之后的数据
	*@index index 节点
	*@return 返回index结点之后的数据
	*/
	public Node findLastNode(int index) {
		if(index < 0 || index > length()) return null;
		Node first = head;
		Node second = head;
		for(int i = 0; i < k - 1; i++) first = first.next;
		while(first != null) {
			first = first.next;
			second = second.next;
		}
		return second;
	}
	
	/**
	*查找第几个链表元素
	*@index 元素下标
	*@return 返回元素
	*/
	public Node find(int index) {
		if(index < 0 || index > length()) return null;
		int i = 0;
		Node currNode = head;
		while(i == (index - 1)) {
			currNode = currNode.next;
			i++;
		}
		return currNode;
	}
	
	//链表反转
	public Node reserve() {
		Node cur = head;
		Node pre = null;
		while(cur != null) {
			Node next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return head;
	}	

	//查找中间链表
	public Node findMiddleNode() {
		Node slow = head;
		Node quick = head;
		while(quick.next != null && quick.next.next != null) {
			slow = slow.next;
			quick = quick.next.next;
		}
		return slow;
	}

	//判断链表是否有环
	public boolean isRinged() {
		if(head == null) return false;
		Node slow = head;
		Node quick = head;
		while(quick.next != null && quick.next.next != null) {
			slow = slow.next;
			quick = quick.next.next;
			if(slow == quick) return ture;
		}
		return false;
	}

	//获取列表最后一个节点
	public Node getLastNode() {
		Node cur = head;
		while(cur.next != null) {
			cur = cur.next;
		}
		return cur;
	}

	//删除节点数据 头部不确定
	public boolean deleteNode(Node node) {
		if(n.next == null) {
			return false;
		} else {
			int temp = n.data;
			n.data = n.next.data;
			n.next.data = temp;
			n.next = n.next.next;
			return ture;
		}
	}

	//判断两个量表是否相交
	public boolean isCross(Node h1, Node h2) {
		Node tem1 = h1;
		Node tem2 = h2;
		while(tem1.next != null) tem1 = tem1.next;
		while(tem2.next != null) tem2 = tem2.next;
		if(tem1 == tem2) return true;
		return false; 
	}

	//判断两个链表是否相交且返回相交节点
	public Node findCrossNode(Node h1, Node h2) {
		if(!isCross(h1, h2)) {
			return null;
		} else {
			int len1 = h1.length();
			int len2 = h2.length();
			Node tem1 = h1.head;
			Node tem2 = h2.head;
			int len = len1 - len2;
			if(len > 0) {
				for(int i = 0; i < len; i++) {
					tem1 = tem.next;
				}
			} else {
				for(int i = 0; i < (-len); i++) {
					tem2 = tem2.next;
				}
			}
			while(tem1 != tem2) {
				tem1 = tem1.next;
				tem2 = tem2.next;
			}
			return tem1;
		}
		
	}

	public int length() {
		if(head == null) return 0;
		int i = 0;
		Node curNode = head;
		while(curNode.next != null) {
			curNode = curNode.next;
			i++;
		}
		return i;
	}

}