目录

一、head头节点

二、插入

1.头插法

2.尾插法

3.按位置插入

首先引入我自定义建立链表对象的类：LinkNode

public class ListNode {
	private int val;
	private ListNode next;
	public ListNode(int value) {
		this.val = value;
	}
	public ListNode() {}
	public ListNode getNext() {
		return this.next;
	}
	public int getVal() {
		return this.val;
	}
	public void setNext(ListNode next) {
		this.next = next;
	}
    public void setVal(int value) {
		this.val = value;
	}
}

一、head头节点

        注意，为了实现链表的各种操作，我们定义一个LinkNode 类的对象head。称为头节点，用于指向链表的起点。LinkNode是我自定义的类，用于实现链表对象的建立。

        定义head：

ListNode head = null;

二、插入

        链表的插入也即链表的构建，把点连成链。因插入位置不同分成三种情况。

1.头插法

        在链表最前端插入数据：

public void HeadInsert(int val) {
		ListNode newNode = new ListNode(val);    首先把val建立成一个新节点
		if(head == null) {    链表为空的情况
			head = newNode;
			return;
		}
		newNode.setNext(head);    链表不为空，则把原第一个节点给到新节点的next
		head = newNode;    新节点成为头节点
	}

2.尾插法

        在链表最后插入数据

public void EndInsert(int val) {
		新建节点存储数据
		ListNode newNode = new ListNode(val); 
		判断头节点是否为空，就是链表是否为空
		if(head == null) {
			head = newNode;    
			return;
		}
		ListNode indexNode = head;    由于头节点head不能改变，召唤替身
		while (indexNode.getNext() != null) {    从头向后遍历，直到某一节点的next
			indexNode = indexNode.getNext();    是空的，意味他是最后一个节点。
		}
		indexNode.setNext(newNode);    让原来最后一个节点的next指向新节点
	}

3.按位置插入

当在链表中间插入值的时候，新节点：new

原插入位置节点：temp

temp前一个节点：pre

插入操作需要做的：

1. new.next = temp
2. pre.next = new

public void Insert(int val,int index) {数值，插入位置
		if(index<0 || index > this.getLength()) {
			System.out.println("index位置不合法");
            return;
		}
		if(index == 0) {
			HeadInsert(val);
		}else if(index == getLength()) {
			EndInsert(val);
		}else {
			ListNode newNode = new ListNode(val);
			ListNode tempNode = head;
			ListNode preNode = null;    pre在temp前1位
			int position = 0;    通过它找到正确插入位置
			while (tempNode != null) {
				if(position == index) {
					newNode.setNext(tempNode);    pre在temp前1位  
              temp指向的是要被插入的位置的值
					preNode.setNext(newNode);
					return;
				}
				preNode = tempNode;
				tempNode = tempNode.getNext();
				position++;
			}
		}
	}