一个链表的题，弄不出来了。求大家帮忙！
日期：2014-05-20 浏览次数：20946 次
一个链表的题，搞不出来了。求大家帮忙！！
//节点类的定义：
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多分钟给你写了个,测试通过,呵呵
//节点类的定义：
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中.
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
