一个链表的题，搞不出来了。求大家帮忙！！
//节点类的定义：
public class Node {
private int data;
public Node next;
public Node()
{
}
public Node(int data)
{
this.data=data;
}
public void setData(int data)
{
this.data=data;
}
public int getData()
{
return data;
}
}
/**
*功能：链表的定义
* */
public class LinkList {
Node head;
int length;
public LinkList() {
length = 0;
}
public void listHeadInsert(int data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
} else {
temp.next = head.next;
head.next = temp;
}
length++;
}
//取元素从1开始, i若为0则返回错误码
public int getData(int i) {
//取元素超过链表范围则返回错误码
if(i <= 0 || i > length){
return -10001;
}
Node temp = head;
int j = 1;
while ((j < i) && temp != null) {
temp = temp.next;
j++;
}
return temp.getData();
}
}
假设有两个按元素值递增有序排列的线性表A和B，均以单链表做存储结构。请编写算法将A表和B表归并成一个按元素值递减的有序（即非递增有序，允许表中含有相同的元素）排列的线性表C，并要求利用原表的（即A表和B表）的节点空间构造C表 。例如:参数为:A={1,2,4,5},B={4,8},结果为:C={8,5,4,4,2,1}。
/**
* 功能：把元素递增排 列的链表A和B合并为C,且C中元素递减排列,使用原空间
* 参数：LinkList类型la
* 参数：LinkList类型 lb
* 返回值：LinkList类型
*/ public static LinkList reverseMerger(LinkList la, LinkList lb) {...............}
[解决办法]
是不是只能用你提供的这几种方法啊？
[解决办法]
说实话,这个链表类写的比较差劲,主要就是那个添加节点的方法,每次都是把节点添加到头节点后...
用了20多分钟给你写了个,测试通过,呵呵
- Java code
/** * 功能：把元素递增排 列的链表A和B合并为C,且C中元素递减排列,使用原空间 * 参数：LinkList类型la * 参数：LinkList类型 lb * 返回值：LinkList类型 * 例如:参数为:A={1,2,4,5},B={4,8},结果为:C={8,5,4,4,2,1}。 */ public static LinkList reverseMerger(LinkList la, LinkList lb) { LinkList lc = new LinkList(); int pointA = la.length; int pointB = lb.length; int pointAY = 1; int pointBY = 1; if(lc.head == null){ if(la.getData(pointA) > lb.getData(pointB)){ lc.listHeadInsert(la.getData(pointA)); pointA--; } else{ lc.listHeadInsert(lb.getData(pointB)); pointB--; } } while(pointAY <= pointA && pointBY <= pointB){ if(la.getData(pointAY) < lb.getData(pointBY)){ lc.listHeadInsert(la.getData(pointAY)); pointAY++; } else{ lc.listHeadInsert(lb.getData(pointBY)); pointBY++; } } if(pointAY <= pointA){ for(int j = pointAY; j <= pointA; j++){ lc.listHeadInsert(la.getData(j)); } } if(pointBY <= pointB){ for(int k = pointBY; k < pointB; k++){ lc.listHeadInsert(lb.getData(k)); } } return lc; } //测试用MAIN方法,上面的方法和这个测试的MAIN方法都丢在LinkList类中写的 public static void main(String[] args){ LinkList la = new LinkList(); LinkList lb = new LinkList(); la.listHeadInsert(1); la.listHeadInsert(5); la.listHeadInsert(4); la.listHeadInsert(2); lb.listHeadInsert(4); lb.listHeadInsert(8); LinkList lc = LinkList.reverseMerger(la, lb); for(int i = 1; i <= lc.length; i++){ System.out.println(lc.getData(i)); } }
[解决办法]
思路就是:先把a,b两个链表的最大元素,也就是两个链表的最后一个元素的值取出来做比较,大的做合并后的链表c的头节点~
然后把a,b里面剩余的接点从小的开始比较,最小的插入到链表c的头节点后面,依次循环插入,最后,如果a中元素已经都插入到c中且b中还有剩余未插的,把b中剩余的元素按照由小到大的顺序插入到c中.
之所以除头节点外其他元素都按照从小到大的顺序插入c,是因为LinkList类的listHeadInsert方法每次都是把元素插入到头节点之后,而不是插到最后一个节点之后.
[解决办法]
楼上的，不合要求哦
不能增加新的空间，所以根本不应该有new LinkList()这样的东东哦
我觉得。
[解决办法]
呵呵,可能有点不符合题意,没有使用原空间
LZ可以对其进行下小改动,思路不便,改动量很小,下班了,回去再说
[解决办法]
再写了一个使用原空间的
- Java code
/** * 功能：把元素递增排 列的链表A和B合并为C,且C中元素递减排列,使用原空间 * 参数：LinkList类型la * 参数：LinkList类型 lb * 返回值：LinkList类型 * 例如:参数为:A={1,2,4,5},B={4,8},结果为:C={8,5,4,4,2,1}。 */ public static LinkList reverseMerger1(LinkList la,LinkList lb){ //保存初始传入的两个链表的值 int staticLengthA = la.length; int staticLengthB = lb.length; //保存插入元素后链表的值 int pointA = la.length; int pointB = lb.length; //当前指向链表中的位置 int pointAY = 1; int pointBY = 1; //循环向la中插入元素，插入完成后la中的值序列为1,8,5,4,4,2,1,2,4,5，里面包含了la中原始值 //头节点为la中初始头节点，从第2个节点到第la.length + lb.length + 1这期间的节点是我们俺顺序排列好的节点 while(pointAY <= pointA && pointBY <= pointB){ if(la.getData(pointAY) < lb.getData(pointBY)){ la.listHeadInsert(la.getData(pointAY)); pointAY = pointAY + 2; pointA++; } else{ la.listHeadInsert(lb.getData(pointBY)); pointA++; pointAY++; pointBY++; } } if(pointAY <= pointA){ for(int j = pointAY; j <= pointA; j++){ la.listHeadInsert(la.getData(j)); } } if(pointBY <= pointB){ for(int k = pointBY; k <= pointB; k++){ la.listHeadInsert(lb.getData(k)); } } //求出合并后链表表(现在只是la的一个子链表)的最后一个节点的位置(也就是上面循环中说la.length + lb.length + 1节点的位置) int mergerPos = staticLengthA + staticLengthB + 1; Node lastNode = la.head; int j = 1; while ((j < mergerPos) && lastNode != null) { lastNode = lastNode.next; j++; } //把la.length + lb.length + 1节点后面的节点链删除，删除完成后la中的值序列为1,8,5,4,4,2,1 lastNode.next = null; la.length = la.length - staticLengthA + 1; //删除原来的头节点，以我们需要的子序列链表的头节点代替 la.head = la.head.next; la.length--; return la; }
[解决办法]
public void listHeadInsert(int data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
} else {
temp.next = head.next;
head.next = temp;
}
length++;
}
这个算法有问题.没有构成递增的.应该是下边这样的
public void listHeadInsert(int data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
} else {
Node t = head;
while(t.next!=null)
{
t = t.next;
}
t.next=temp;
}
length++;
}
[解决办法]
- Java code
package a;public class LinkList { Node head; int length; public LinkList() { length = 0; } public void listHeadInsert(int data) { Node temp = new Node(data); if (head == null) { head = temp; } else { Node t = head; while(t.next!=null) { t = t.next; } t.next=temp; } length++; } // 取元素从1开始, i若为0则返回错误码 public int getData(int i) { // 取元素超过链表范围则返回错误码 if(i <= 0 || i > length){ return -10001; } Node temp = head; int j = 1; while ((j < i) && temp != null) { temp = temp.next; j++; } return temp.getData(); } /** * 功能：把元素递增排 列的链表A和B合并为C,且C中元素递减排列,使用原空间 * 参数：LinkList类型la * 参数：LinkList类型 lb * 返回值：LinkList类型 */ public static LinkList reverseMerger(LinkList la, LinkList lb) { Node []a=new Node[la.length]; Node []b = new Node[lb.length]; Node temp=la.head; //两个for循环,复制所有的元素引用 for(int i=0;i<a.length;i++) { a[i]=temp; temp = temp.next; } temp=lb.head; for(int i=0;i<b.length;i++) { b[i]=temp; temp = temp.next; } int aindex=a.length-1;//从最后的下标去取 int bindex=b.length-1;//从最后的下标去取 LinkList thead=null; //判断哪个链表最后结点值大 if(a[aindex].getData()<b[bindex].getData()) { thead=lb; temp=b[bindex]; bindex--;//如果是b的最后结点大,那么b最后一个元素不用比较了 }else { thead=la; temp=a[aindex]; aindex--;//如果是a的最后结点大,那么a最后一个元素不用比较了 } thead.head=temp; while(true) { if(aindex!=-1&&bindex!=-1) { if(a[aindex].getData()>b[bindex].getData()) { temp.next=a[aindex]; aindex--; }else { temp.next=b[bindex]; bindex--; } }else { if(aindex==-1 && bindex!=-1) { temp.next=b[bindex]; bindex--; } if(bindex==-1 && aindex!=-1) { temp.next=a[aindex]; aindex--; } } temp.next.next=null;//把以前的关系断开 temp=temp.next; //所以的结点遍历结束 if(aindex==-1&& bindex==-1) { break; } } return thead; } public static void main(String[] args){ LinkList la = new LinkList(); LinkList lb = new LinkList(); la.listHeadInsert(1); la.listHeadInsert(2); la.listHeadInsert(4); la.listHeadInsert(5); lb.listHeadInsert(4); lb.listHeadInsert(8); LinkList lc = LinkList.reverseMerger(la, lb); Node t = lc.head; while(t!=null) { System.out.println(t.getData()); t = t.next; } }}
[解决办法]
- Java code
public static LinkList reverseMerger(LinkList la, LinkList lb) { LinkList t = null; Node na = la.head; Node nb = lb.head; //找出小最结点所在的链表 if(na.getData()<nb.getData()) { t = la; na=na.next;//最小的不需要再去遍历 }else { t = lb; nb = nb.next;//最小的不需要再去遍历 } t.head.next=null;//断开关系,否则容易造成死循环. //遍历两个链表,找出最小未排的结点,插入到已排链表头 Node temp = null; while(!(na==null && nb==null)) { //两个都没有遍历完 if(na!=null && nb!=null) { if(na.getData()<nb.getData()) { temp = na; na = na.next; }else { temp=nb; nb = nb.next; } }else { //lb遍历完 if(na!=null && nb==null) { temp = na; na = na.next; } //lb遍历完 if(nb!=null && na==null) { temp = nb; nb = nb.next; } } //因为每次找到的都是未排最小的,对于已经排的来说是大的,所以插入到链表头 if(temp!=null) { temp.next = t.head; t.head = temp; } } return t; }
[解决办法]
TO AWUSOFT :
你把给定的条件都改了,那还有什么用啊.....listHeadInsert方法是给定的~要是可以重写LinkList类里的方法的话那这问题还叫问题?
这题比较让人费解的就是不知道题目的作者为什么这样写listHeadInsert方法,作为一个链表的添加节点方法怎么能每次都添加到头节点后呢~
[解决办法]
呵呵,今天上午发上来的方法完全是符合要求的,问题解决了要尽快结帖撒