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