代码如下
/**
* 单链表实现
* @param <T>
*/
public class SinglyLinkedList<T extends Comparable<? super T>> {
private Node<T> head; // 指向链表头结点
private Node<T> tail; // 指向链表尾结点
private int size; // 链表长度
public SinglyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
/**
* 向链表头部添加元素
*
* @param val
*/
public void addFirst(T val) {
Node<T> new_node = new Node<T>(val, null);
if (!isEmpty()) {
new_node.next = head;
head = new_node;
} else {
this.head = new_node;
this.tail = new_node;
}
size++;
}
/**
* 向链表尾部添加元素
*
* @param val
*/
public void addLast(T val) {
Node<T> new_node = new Node<T>(val, null);
if (!isEmpty()) {
tail.next = new_node;
tail = tail.next;
} else {
this.head = new_node;
this.tail = new_node;
}
size++;
}
/**
* 有序添加元素(自定义升序排序)
*
* @param val
*/
public void add(T val) {
Node<T> new_node = new Node<T>(val, null);
if (!isEmpty()) {
if (this.tail.item.compareTo(new_node.item) <= 0) {
tail.next = new_node;
tail = tail.next;
} else {
Node<T> p_node = this.head;
Node<T> q_node = p_node;
while (p_node != null) {
if (new_node.item.compareTo(p_node.item) < 0) {
break;
}
q_node = p_node;
p_node = p_node.next;
}
new_node.next = p_node;
q_node.next = new_node;
}
} else {
this.head = new_node;
this.tail = new_node;
}
size++;
}
/**
* 插入指定位置
*
* @param index
* @param val
*/
public void insert(int index, T val) {
Node<T> new_node = new Node<T>(val, null);
if (isEmpty()) {
head = new_node;
} else {
if (index > size + 1) {
System.out.println("下标超限");
} else {
Node<T> pre = findIndex(index - 1);
new_node.next = pre.next;
pre.next = new_node;
}
}
size++;
}
/**
* 查找指定位置的结点
*
* @param index
* @return
*/
public Node<T> findIndex(int index) {
int i = 1;
Node<T> p = head;
while (p != null) {
if (i == index) {
return p;
}
i++;
p = p.next;
}
return null;
}
/**
* 寻找链表中指定结点
*
* @param val
* @return
*/
public Node<T> find(T val) {
Node<T> x = this.head;
Node<T> t = new Node<T>(val, null);
while (x != null) {
if (x.item.compareTo(t.item) == 0) {
return x;
}
x = x.next;
}
return null;
}
/**
* 判断链表中是否含有指定的Val
*
* @param val
* @return
*/
public boolean containsVal(T val) {
Node<T> p_node = this.head;
Node<T> q_node = new Node<T>(val, null);
while (p_node != null) {
if (p_node.item.compareTo(q_node.item) == 0) {
return true;
}
p_node = p_node.next;
}
return false;
}
/**
* 反转链表
*
* @param head
* @return 反转后的头指针
*/
public Node<T> reverseList(Node<T> head) {
Node<T> new_head = null;
while (head != null) {
Node<T> p = head.next;
head.next = new_head;
new_head = head;
head = p;
}
return new_head;
}
/**
* 删除链表中重复元素
*
* @return 删除重复元素后的头指针
*/
public Node<T> deleteDuplicates() {
Node<T> current = this.head;
while (current != null && current.next != null) {
if (current.item.compareTo(current.next.item) == 0) {
current.next = current.next.next;
size--;
} else {
current = current.next;
}
}
return head;
}
/**
* 删除链表中指定元素
*
* @param head
* @param val
* @return
*/
public void remove(T val) {
Node<T> dummyNode = new Node<T>(val, null);
dummyNode.next = head;
Node<T> prev = dummyNode;
while (prev.next != null) {
if (prev.next.item == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
}
/**
* 合并两个有序链表（迭代）
*
* @param l1
* @param l2
* @return 合并后的头结点
*/
public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
Node<T> prehead = new Node<T>();
Node<T> prev = prehead;
while (l1 != null && l2 != null) {
if (l1.item.compareTo(l2.item) <= 0) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
/**
* 将链表以数组的形式返回
*
* @return
*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<T> x = head; x != null; x = x.next)
result[i++] = x.item;
return result;
}
/**
* 判断链表是否为空
*
* @return head == null
*/
private boolean isEmpty() {
return this.head == null;
}
public Node<T> getHead() {
return head;
}
public Node<T> getTail() {
return tail;
}
public int getsize() {
return size;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
Node<T> p_node = this.head;
while (p_node != null) {
sb.append(p_node.item + " ");
p_node = p_node.next;
}
return sb.toString();
}
public void Print(){
Node<T> p = this.head;
while(p != null){
System.out.println(p.item);
p = p.next;
}
}
}
Q.E.D.
