问题描述
- 用c语言编程，关于链表的
-
请教各位大神：实现创建链表，输出链表两个函数怎么编程序。。。
输入两个非降序列，转换成两个非升序列，合并成一个非升序列，用链表实现
解决方案
解决方案二：
您这问题也太多了吧。创建链表都要问，创建链表书上都有。第一行的问题自己想办法。
第二行问题我回答下，可以想象一下当一个链表从非降序转化成非升序时，其实就是将链表逆序。可以新建一个链表，然后遍历要逆序的链表，每次将每个元
素插入到新链表的第一个位置。这样遍历结束后新链表就是非升序的。
两个非降序列，转换成两个非升序列，合并成一个非升序列。其实道理是一样的，多了比较而已，
第一步 新建一个新的链表
第二步 定义三个指着分别指向非降序链表（p1，p2），和新生成的链表（p3）
第三歩 比较比较p1和p2所指的元素大小，哪个元素大就讲哪个元素插入到新链表中的第一的位置上，并将该指着移动到下一个位置上。
重复做第三步，知道摸一个非降序链表遍历结束，将另一个还剩下的元素遍历每个元素还是直接插入到新链表的首部。
解决方案三：
参考：http://blog.csdn.net/pf4919501/article/details/38818335
建议楼主先自己试着写一下，有问题的话可以再发上来
解决方案四：
链表的创建。。。。。。。。。还是看书吧。先把链表的定义搞清楚.楼上回答的已经很清楚了。这里我补充一下代码，哈哈。
两个非降序列，转换成两个非升序列：就是先分别反转链表。反转链表代码如下
ListNode* reverseList(ListNode* head) {
if(NULL==head)
{
return head;
}
ListNode* prev=head;
ListNode* cur=head->next;
ListNode* tmp=NULL;
prev->next=NULL;
while(cur!=NULL)
{
tmp=cur->next;
cur->next=prev;
prev=cur;
cur=tmp;
}
return prev;
}
大意就是设两个指针，两个指针指向相邻的结点。然后反转相邻的两个结点，然后指针向前走，再反转指向的两个结点。不断重复，一直到链表结尾。就可以了。
除了这种方法以外，还可以用递归。代码如下：
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)
{
return head;
}
ListNode* tmp;
tmp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tmp;
}
反转完链表以后。接下来就是将两个链表merge成一下单链表。楼上说的很清楚，但是需要额外申请空间。这里有一个方法不用申请内存。如下：
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)
{
return head;
}
ListNode* tmp;
tmp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tmp;
}
依然是递归。如果不懂递归。。。。。。。。看书去。
解决方案五：
上面的merge链表函数写错了。更正如下（并补充非递归的写法）
递归：
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL) return l2;
if(l2==NULL) return l1;
ListNode* Head=NULL;
if(l1->valval)
{
Head=l1;
Head->next=mergeTwoLists(l1->next,l2);
}
else
{
Head=l2;
Head->next=mergeTwoLists(l1,l2->next);
}
return Head;
}
非递归：
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL&&l2==NULL) return NULL;
vector NodeVec;
while(l1!=NULL&&l2!=NULL)
{
if(l1->val>l2->val)
{
NodeVec.push_back(l2);
l2=l2->next;
}
else
{
NodeVec.push_back(l1);
l1=l1->next;
}
}
while(l1!=NULL)
{
NodeVec.push_back(l1);
l1=l1->next;
}
while(l2!=NULL)
{
NodeVec.push_back(l2);
l2=l2->next;
}
int i=0;
for(;i
{
NodeVec[i]->next=NodeVec[i+1];
}
NodeVec[i]->next=NULL;
return NodeVec[0];
}