一个链表的题，搞不出来了。求大家帮忙！！

Question

//节点类的定义：
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) {...............}

Answer 1

节点类和链表类要用已经定义好的。只有头结点和下一结点。方法名是public static LinkList reverseMerger(LinkList la, LinkList lb) {...............} 
按照题意实现这个方法。越想越乱，所以请各位高手来帮忙!!
先谢谢了！

Answer 2

说实话,这个链表类写的比较差劲,主要就是那个添加节点的方法,每次都是把节点添加到头节点后...
用了20多分钟给你写了个,测试通过,呵呵        /** 
* 功能：把元素递增排 列的链表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));
}

}

Answer 3

思路就是:先把a,b两个链表的最大元素,也就是两个链表的最后一个元素的值取出来做比较,大的做合并后的链表c的头节点~
然后把a,b里面剩余的接点从小的开始比较,最小的插入到链表c的头节点后面,依次循环插入,最后,如果a中元素已经都插入到c中且b中还有剩余未插的,把b中剩余的元素按照由小到大的顺序插入到c中.
之所以除头节点外其他元素都按照从小到大的顺序插入c,是因为LinkList类的listHeadInsert方法每次都是把元素插入到头节点之后,而不是插到最后一个节点之后.

Answer 4

楼上的，不合要求哦
不能增加新的空间，所以根本不应该有new LinkList()这样的东东哦
我觉得。

Answer 5

再写了一个使用原空间的/** 
* 功能：把元素递增排 列的链表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;
}

Answer 6

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++; 
} 

Answer 7

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;
 }
 }
} 

Answer 8

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;
 } 
这是另一个算法.

Answer 9

TO AWUSOFT :
你把给定的条件都改了,那还有什么用啊.....listHeadInsert方法是给定的~要是可以重写LinkList类里的方法的话那这问题还叫问题?
这题比较让人费解的就是不知道题目的作者为什么这样写listHeadInsert方法,作为一个链表的添加节点方法怎么能每次都添加到头节点后呢~