JAVA单链表的简单操作（递增单链表插入数据，链表逆置，链表逆序合成）
版权申诉
178 浏览量
2020-12-21
22:30:42
上传
评论
收藏 68KB PDF 举报
JAVA单链表的简单操作（递增单链表插入数据，链表逆置，单链表的简单操作（递增单链表插入数据，链表逆置，
链表逆序合成）链表逆序合成）
JAVA写一个单链表写一个单链表
1、已知带头结点的动态单链表、已知带头结点的动态单链表 L 中的结点是按整数值递增排序的，试写一中的结点是按整数值递增排序的，试写一 算法将值为算法将值为 x 的结点插入到表的结点插入到表 L 中，使中，使 L 仍然有仍然有
序。要求算法的时间复杂度为序。要求算法的时间复杂度为 O(n)，空间复杂度为，空间复杂度为 O(1)。。
2、设计一算法，逆置带头结点的动态链表、设计一算法，逆置带头结点的动态链表 L。要求利用原表的结点空间，。要求利用原表的结点空间， 并要求用尽可能少的时间完成。并要求用尽可能少的时间完成。
3、假设有两个按元素值递增有序的线性表、假设有两个按元素值递增有序的线性表 A 和和 B，均以单链表作存储结构，，均以单链表作存储结构， 试编写算法将试编写算法将 A 表和表和 B 表归并成一个按元素值表归并成一个按元素值
递减有序的线性表性表递减有序的线性表性表 C，并要求，并要求 利用原表的空间存放利用原表的空间存放 C，并要求用尽可能少的时间完成。，并要求用尽可能少的时间完成。
如何插入一段漂亮的代码片如何插入一段漂亮的代码片
要求一：不破坏表的顺序插入元素，时间复杂度O（n）
一个for循环即可解决
//
public void Insert_order(int e){
Node current = header;
if(header == null) //空表直接尾部加
add(e);//在尾部添加元素
int i;
for(i=0;i=e){//如果某个结点的指大于等于输入值
if(i==0) {//如果是在头节点，直接加在前面
addHead_e(e);//在头部添加元素
break;
}
Node p=this.getNodeByIndex(i-1);//指定位置的前一个节点
p.next=new Node(e,p.next);//这是不在首位的情况，获取当前节点的前一个节点并将e插在它后面，同时新节点的指向是原节点的下一个节点
size++;
break;
}
}
if(i==size)//如果循环没有被break结束，那么i的值与size的值相等，
add(e);//这说明这个元素比原链表中任何一个都大，直接在尾部添加节点即可
//System.out.println(size);
}
用到的add(e)和addHead_e(e)方法：
//直接在尾部插入元素
public void add(int e){
if(header==null) {
header = new Node(e, null);
tail = header;
}
else{
Node p=new Node(e,null);
tail.next=p;
tail=p;
}
size++;
}
//在表头插入元素
public void addHead_e(int e){
Node p=new Node(e,null);
p.next=header;
header=p;
if(header.next==null)
tail=header;
size ++;
}
用到的getNodeByIndex(index)方法：
// 获取指定节点
private Node getNodeByIndex(int index){
if(index = size)
throw new IndexOutOfBoundsException("索引超出线性表范围");
Node current = header;//从header开始遍历
for(int i=0; i<size && current!=null; i++,current=current.next){
if(i == index)
return current;
}
return null;
评论0
最新资源