链表简介
代码实现
package com.chenxixuexi;
/**
* 泛型链表
* 单链表逆置数据--节点
* 求单链表倒数第K节点
* 求两个单链表 是否相交 相交交点
* 判断单链表是否有环？有求出环的入口点 求环的长度？
* 合并两个递增的单链表
* @author 14831
*
* @param <T>
*/
public class Link<T> {
private Entry<T> head = new Entry<T>(); //指向头结点的引用
/**
* 节点类
* @author 14831
*
* @param <T> 类型
*/
class Entry<T>{//Entry Node
T data;
Entry<T> next;
/**
* 头结点空构造方法
*/
public Entry() {
data = null;
next = null;
}
/**
* 构造节点
* @param a
*/
public Entry(T a) {
data = a;
next = null;
}
}
/**
* 头插法
* @param val 需要插入的数据
*/
public void insertHead(T val)
{
//有这么一个节点
Entry<T> cur = new Entry<T>(val);
cur.next = head.next;
head.next = cur;
}
/**
* 尾插法
* @param val 需要插入的值
*/
public void insertTail(T val)
{
Entry<T> cur = head;
while(cur.next!= null) //循环直到cur.next为空 把cur弹出
{
cur = cur.next;
}
cur.next = new Entry<T>(val);//给cur.next 赋值为新节点的地址
}
/**
* 插入到pos位置 从有数据开始为0下标
* @param pos 位置序号
* @param val 插入的值
*/
public void insertPos(int pos,T val)
{
Entry<T> cur = head; //获取头结点
int count = 0;
if(pos<0||pos>getLength()) //如果需要中断操作，只需要在此return即可
System.out.println("下标"+pos+"不合法,自动插入到最后位置");
while(cur.next!= null) //循环直到cur.next为空 把cur弹出 及如果没找到就会把元素插入到最后面
{
if(count == pos)
break;
count++;
cur = cur.next;
}
Entry<T> cur1 = new Entry<T>(val);
cur1.next = cur.next;
cur.next = cur1;
}
/**
* 遍历输出数组
*/
public void show()
{
Entry<T> cur = head.next; //获取到第一个节点
System.out.print("[");
while(cur!=null) //如果cur不是null
{
System.out.print(cur.data+" "); //输出
cur = cur.next; //向下递进
}
System.out.println("]");
}
/**
* 获得链表长度
* @return 链表长度
*/
public int getLength()
{ int count=0;
Entry<T> cur = head.next; //获取到第一个节点
while(cur!=null) //如果cur不是null
{
count++; //计数
cur = cur.next; //向下递进
}
return count;
}
/**
* 翻转链表
*/
public void Reversal()
{
Entry<T> p = head.next,p1 = null,p2 = null;
while(p!=null){
p1 = p.next; //设置p1是p结点的后继结点,即用p1来保持p的后继结点
p.next = p2; //链接,使p.next指向p结点的前一个结点
p2 = p; //p2向后移一步
p = p1; //p向后移一步
}
head.next = p2; //head.next指向最后一个结点
}
/**
* 求倒数第K个元素
*
* @param k 序号
* @return 所求元素
*/
public T BackWardsToK(int k)
{
if(k>getLength()-1){ //判错
System.err.println("超越限制,下标不合法，倒数下标从0开始");
return null;
}
int key = getLength()-k;
Entry<T> cur = head; //获取头结点
int count = 0;
while(cur.next!= null) //循环直到cur.next为空 把cur弹出 及如果没找到就会把元素插入到最后面
{
if(count == key)
break;
count++;
cur = cur.next;
}
return cur.data;
}