6-4 链表的拼接

6-4 链表拼接（20 分）

本题要求实现一个合并两个有序链表的简单函数。链表结点定义如下：

struct ListNode {
    int data;
    struct ListNode *next;
};

函数接口定义：

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);

其中 list1 和 list2 是用户传入的两个按 data 升序链接的链表的头指针；函数 mergelists 将两个链表合并成一个按 data 升序链接的链表，并返回结果链表的头指针。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); /*裁判实现，细节不表*/
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode  *list1, *list2;

    list1 = createlist();
    list2 = createlist();
    list1 = mergelists(list1, list2);
    printlist(list1);
	
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1 3 5 7 -1
2 4 6 -1

输出样例：

1 2 3 4 5 6 7 

答案

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
    struct ListNode *poi1,*poi2;
    poi1=list1;
    int len1=0;
    while(poi1!=NULL)
    {
        poi1=poi1->next;
        len1++;
    }
    //printf("长度为%d\n",len1);
    poi2=list2;
    int len2=0;
    while(poi2!=NULL)
    {
        poi2=poi2->next;
        len2++;
    }
    //printf("长度为%d\n",len2);
    int nums[len1+len2];
    poi1=list1;
    int i=0;
    while(poi1!=NULL)
    {
        nums[i++]=poi1->data;
        poi1=poi1->next;
    }
    poi2=list2;
    while(poi2!=NULL)
    {
        nums[i++]=poi2->data;
        poi2=poi2->next;

    }
    int len=len1+len2;
    if(len==0)
        return NULL;
    int ii;
    int iii;
    for(ii=len-1;ii>=0;ii--)
    {
        for(iii=0;iii<=ii-1;iii++)
        {
            if(nums[iii]>nums[iii+1])
            {
                int tt=nums[iii+1];
                nums[iii+1]=nums[iii];
                nums[iii]=tt;
            }
        }
    }
    struct ListNode *head=NULL;
    struct ListNode *tail=NULL;
    struct ListNode *poi;
    head=(struct ListNode *)malloc(sizeof(struct ListNode));
   // printf("长度为%d\n",len);
    if(len>=1)
    {
        poi=head;
        head->data=nums[0];
        head->next=tail;
        for(i=1;i<=len-1;i++)
        {
            struct ListNode *temp;
            temp=(struct ListNode *)malloc(sizeof(struct ListNode));
            temp->data=nums[i];
            poi->next=temp;
            temp->next=tail;
            poi=poi->next;
        }
    }
    return head;
};

这种方法是最为直观的一种。运用到了position指针。（为了保持head不变）。

另一种创建链表的方法：

struct ListNode  *newlist = NULL;
      struct ListNode  *endlist = NULL;
      struct ListNode  *q;
      for(i = 0; i < num; i++)
      {
          q = (struct ListNode  *)malloc(sizeof(struct ListNode));
          q->data = temp[i];
          if(newlist == NULL)
          {
              newlist = q;
              newlist->next = NULL;
          }
            if(endlist != NULL)
         {
            endlist->next = q;
         }
         endlist = q;
         endlist->next = NULL;
      }
      return newlist;

注意，一个指针每开辟一次空间就换一个位置。

同时，一个指针同时只能指向一个位置。

画图虚线为指针，时限为下一个