链蒙本人的各种方法

1线性链表是由结点组成的，一个结点又是由数据域和指针域两部分组成的，数据域中存放的就是数据元素， 指针域中的指针值对应的就是存储器中的一个存储地址。

2每一个结点所占用的空间是一段连续的空间。不同结点的物理存储位置可能是相邻的，也可能不相邻。

3每个结点都是在程序运行时动态创建的，并不知道每个结点的存储位置，需要关心的是数据元素之间的逻辑关系，即用指针来表示出的关系。

4整个链表都是由一个头指针Head指出，也就是说头指针唯一确定该链表。

5单链表就是说单向链表，也就是只有一个指针域。

这些概念性的知识点就是为了实际操作做铺垫，现在就说一下方法：

定义一个结点类：

public class Node {
    Object obj;   //数据域
    Node next;    //指针值
   // Node index;
    public Node(Object obj){
    	this.obj=obj;
    	//this.next=next;
    }
}

 定义一个链表类：

public class LinkList {
	Node head = null;
	Node last = head;
             public static void main(String[] args) {
      }
}

 在此类中定义方法，第一个添加元素方法：

public void add(Object obj) {
		Node node = new Node(obj);
		if (head == null) {
			head = node;
			last = node;
		} else {
			last.next = node;
			last = node;
		}
	}

 无论是更改或者删除一个元素，前提是要可以通过索引得到该元素，通过索引得到该元素的前提是先得到该链表的长度：

//得到链表长度
	public int getlength() {
		int length = 0;
		Node node = head;//获取头结点，则可获得此链表，但不能直接用头节点，因为头节点会往后移
		while (node != null) {
			length++;
			node = node.next;
		}
		return length;
	}

 

通过索引得到元素的方法：

//通过索引得到链表中元素的值
	public Node getNode(int index) {
		if (index >= 0 && index < this.getlength()) {
			Node node = head;
			while (node != null) {
				if (count == index)//当当前计数等于索引，则跳出循环
					break;
				count++; 
				node = node.next; //继续往下数
			}
			return node;
		}
		return null;
	}

 

删除和更改方法就容易得多了：

// 从表头向表尾计数
	public void delete(int index) {
				if (index < 0 || index >= this.getlength()) {
			throw new RuntimeException("下标越界");
		}
		if (index == 0) { //如果是头结点
			head = head.next;
		} else {
			Node n1 = this.getNode(index - 1);
			Node n2 = this.getNode(index + 1);
			n1.next = n2;
		}
	}
//根据索引更改链表中的元素
	public void update(int index, Node node) {
		Node node2 =  getNode(index);
		node2 = node;
	}

 遍历打印该链表（递归）：

public void printLinkList(Node head) {
		if (head != null) {
			System.out.println(head.obj);
			Node node = head.next;
			printLinkList(node);
		}
	}

 那么怎样判断一个链表上是否有环呢？因为本人之前有写根据下标得到结点的方法，所以这个方法基于那个方法写就容易得多了~：

//判断一个链表是否有环
	private boolean isCircle(){
		for(int i=0;i<list.getlength();i++){
			for(int j=1;j<list.getlength();j++){
				if(getNode(i).next==getNode(j).next){//若两个指针指向同一个结点，则代表有环
					System.out.println("环入口结点为第"+i+"个"+"该链表上有环");
					return true;	
				}
			}
		}
		return false;
	}

 

关于单链表反转，本来也想用getNode（），但是不知怎么回事总报错（得再想想），所以就寻了一个方法，这个方法很好玩，它是建了一个空表头，这表头就放在那里，通过改换指针指向，将后面的所有结点反转，当然是真的反转而不是仅仅改变了元素的值，不过说实在的，下面那五个赋值当时把我真绕懵了（其实我真是看中了这5个赋值），但觉得这楼主写的挺好，就盗用了~

//单链表反转
	private Node tranverse(Node head){
		Node n=head.next;
		Node next=null;
		Node nextnext=null;
		if(n==null||n.next==null){
			return head;
		}
		while(n.next!=null){//递归了
			next=n.next;
			nextnext=next.next;
			next.next=head.next;
			head.next=next;
			n.next=nextnext;
		}
		return head;
	}

 判断两个单链表是否相交，其实也就是判断两个链表中是否有指针指向相同的结点了，只需两个链表分别遍历循环嵌套，之后再用getNode()方法，之后进行判断是否相等即可~

链表内容真的好多，还有约瑟夫环，排序，合并等好多问题。

所以，未完待续~