搜索
有爱,有技术,有你^_^)y
╱人◕‿‿◕人╲订下契约(注册新用户)

合作站点账号登陆

QQ登录

只需一步,快速开始

快捷导航
查看: 621|回复: 10
收起左侧

关于链表的链接问题。

[复制链接]

该用户从未签到

11

主题

37

好友

1万

积分

第一章

积分
18487
发表于 2013-4-13 23:05:48 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要 登录 才可以下载或查看,没有账号?╱人◕‿‿◕人╲订下契约(注册新用户)

x
好吧。其实我用笨办法做出来了。但是在OJ上和别人的一比。时间和内存占用看得我想哭。

就是把2个链表 按元素的从大到小链接起来。
input :
2 3
1 6
2 4 4

ouput:
6 4 4 2 1

第一排就是链表A和链表B元素个数;
第二排就是链表A的元素;
第三排就是聊表B的元素。


我的方法比较笨。先把它们链接起来。然后冒泡。
现在想直接对它们进行链接。求解。
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复

使用道具 举报

该用户从未签到

11

主题

37

好友

1万

积分

第一章

积分
18487
 楼主| 发表于 2013-4-14 11:33:09 | 显示全部楼层
[mw_shl_code=cpp,true]int ListLinksort(LinkList La,LinkList Lb)
{
    LinkList temp=new LNode;
    while(Lb->next!=NULL&&La->next!=NULL)
    {
        if(La->next->data<Lb->next->data&&La->next->next==NULL)
        {La->next->next=Lb->next;break;}
        if(La->next->data<Lb->next->data&&Lb->next->data<=La->next->next->data)
        {
            temp->next=Lb->next->next;
            Lb->next->next=La->next->next;
            La->next->next=Lb->next;
            Lb->next=temp->next;
        }
        else if(La->next->data>=Lb->next->data)
        {
            temp->next=Lb->next->next;
            Lb->next->next=La->next;
            La->next=Lb->next;
            Lb->next=temp->next;
        }
        La=La->next;
    }
}
int Listexchange(LinkList L)
{
    LinkList Head=new LNode;
    Head=L;
    L=L->next;
    LinkList x=new LNode;
    LinkList y=new LNode;
    x=L->next,L->next=NULL,y=L,L=x;
    while(L->next!=NULL)
    x=L->next,L->next=y,y=L,L=x;
    L->next=y;
    Head->next=L;
}[/mw_shl_code]
我又笨了。用了2个函数。先从小到大。再逆序。
一开始就从大到小。我怕我会混乱。
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

258

主题

314

好友

3万

积分

第二章

积分
35715
发表于 2013-4-14 13:58:13 | 显示全部楼层
话说链表A、B原来是有序的吗?看输入好像是这样的?
如果A、B都有序的话可以O(m+n)合并
如果不是的话就需要排序了,最好先转化成数组,然后用快排之类的排序算法,链表不能随机访问元素,很多排序算法不能直接用于链表
不过貌似在链表上可以直接用归并排序
博客什么的求人气 http://bimania.org
回复 支持 反对

使用道具 举报

该用户从未签到

14

主题

22

好友

7919

积分

序章

积分
7919
发表于 2013-4-14 22:35:00 | 显示全部楼层
确实. 链表自己处理排序等问题, 有些浮肿,

想到一种办法, 操作链表节点的地址, 而不是数据,  链表的优势在于对于数据的连,断,加,减, 如果只操作节点地址的话开销会相对小一点,
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

11

主题

37

好友

1万

积分

第一章

积分
18487
 楼主| 发表于 2013-4-15 07:54:36 | 显示全部楼层

都是 从小到大排好了的。不过可能会出现  A:1 3 5.    B: 2 4 6.交叉什么的。
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

11

主题

37

好友

1万

积分

第一章

积分
18487
 楼主| 发表于 2013-4-15 07:56:00 | 显示全部楼层
jains521 发表于 2013-4-14 22:35
确实. 链表自己处理排序等问题, 有些浮肿,

想到一种办法, 操作链表节点的地址, 而不是数据,  链表的优势在 ...

话说能用指针么?指向链表的地址?
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

3

主题

37

好友

1万

积分

第一章

积分
11825
发表于 2013-4-15 08:25:26 | 显示全部楼层
汝欠咱的一生 发表于 2013-4-15 07:54
都是 从小到大排好了的。不过可能会出现  A:1 3 5.    B: 2 4 6.交叉什么的。 ...

都排好了就不用怎么排序了吧。。。。把两个链表归并下就行了。
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

14

主题

22

好友

7919

积分

序章

积分
7919
发表于 2013-4-15 09:20:36 | 显示全部楼层
汝欠咱的一生 发表于 2013-4-15 07:56
话说能用指针么?指向链表的地址?

用的是指向指针的指针,
具体实现还没构思好
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

258

主题

314

好友

3万

积分

第二章

积分
35715
发表于 2013-4-15 12:27:15 | 显示全部楼层
汝欠咱的一生 发表于 2013-4-15 07:54
都是 从小到大排好了的。不过可能会出现  A:1 3 5.    B: 2 4 6.交叉什么的。 ...

那样就是归并下咯
用一个空的链表C来存放结果
每次看一下两个链表头部的元素,比较一下哪个比较小,把小的插入到C中,然后把原始的元素删掉
博客什么的求人气 http://bimania.org
回复 支持 反对

使用道具 举报

该用户从未签到

11

主题

37

好友

1万

积分

第一章

积分
18487
 楼主| 发表于 2013-4-15 22:31:29 | 显示全部楼层
轻舟过 发表于 2013-4-15 12:27
那样就是归并下咯
用一个空的链表C来存放结果
每次看一下两个链表头部的元素,比较一下哪个比较小,把小 ...

我开始也这么想的。但是要求不开辟新的空间。利用原来的。
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

该用户从未签到

3

主题

37

好友

1万

积分

第一章

积分
11825
发表于 2013-4-16 08:40:37 | 显示全部楼层
汝欠咱的一生 发表于 2013-4-15 22:31
我开始也这么想的。但是要求不开辟新的空间。利用原来的。

只是定义了一个head指针变量不算开辟新空间吧
签名被小宅喵吞掉了~~~~(>_<)~~~~
回复 支持 反对

使用道具 举报

本版积分规则

小黑屋|手机版|技术宅(Z站|基宅) ( 粤ICP备18082987号-1 )

GMT+8, 2025-5-2 00:10 , Processed in 0.101504 second(s), 18 queries , Redis On.

Copyright © 2018 技术宅社区

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表