链表的生成与合并

一个很经典的链表程序，在笔试中经常会考到这个题目。

#include <stdio.h>

#include <windows.h>

// 链表定义

typedef struct LNode{

 int  data;

 LNode *next;

}LNode, *LinkList;

//

// 函数声明

//

void  CreateList(LinkList &L);

int   GetElem(LinkList L, int i);

LinkList MergeList(LinkList L1,LinkList L2);

void  SortList(LinkList &L,BOOL flag);

void  PrintList(const LinkList &L);

int main()

{

 LinkList L1;

 LinkList L2;

 printf("第一个链表：/n");

 CreateList(L1);

 PrintList(L1);

 printf("第二个链表：/n");

 CreateList(L2);

 PrintList(L2);

 printf("合并后的链表：/n");

 LinkList L = MergeList(L1,L2);

 PrintList(L);

 return 0;

}

//

// 创建链表L(遇到-1时结束)

//

void CreateList(LinkList &L)

{

 LinkList head;

 LinkList p;

 // 建立第一个结点

 L = (LinkList)malloc(sizeof(LNode));

 L->next = NULL;

 scanf("%d",&L->data);

 // 保存头结点

 head = L;

 int iData;

 while (TRUE)

 {

  scanf("%d",&iData);

  if (iData == -1)

   break;

  // 建立一个结点p

  p = (LinkList)malloc(sizeof(LNode));

  p->data = iData;

  p->next = NULL;

  // 把L指针指向结点p

  L->next = p;

  L = L->next;

 }

 // 把指针移动到头结点

 L = head;

}

//

// 提取出链表L中第i个结点的值

//

int GetElem(LinkList L, int i)

{

 LinkList p;

 int j = 1;

 p = L;

 while (p && (j < i))

 {

  p = p->next;

  ++j;

 }

 if ((!p) || (j>i))

 {

  return -1;

 }

 return (p->data);

}

//

// 合并链表L1和L2(递归法)

//

LinkList MergeList(LinkList L1,LinkList L2)

{

 if(L1 == NULL)

 {

  return L2;

 }

 if(L2 == NULL)

 {

  return L1;

 }

 LinkList head;

 if(L1->data <= L2->data)

 {

  head = L1;

  head->next = MergeList(L1->next,L2);

 }

 else

 {

  head = L2;

  head->next = MergeList(L1,L2->next);

 }

 return head;

}

//

// 合并链表L1和L2(非递归)

//

//

// 输出链表的所有结点

//

void PrintList(const LinkList &L)

{

 LinkList p;

 p = L;

 while(p)

 {

  printf("%d -> ",p->data);

  p = p->next;

 }

 printf("NULL/n");

}