将两个有序链表合并为一个链表任然有序C语言_c语言两个有序单链表合并为一个有序链表

将两个有序链表合并为一个链表任然有序，两个链表都是从大到小或者从小到大。
方法：
1.将两个链表连起来，对所有元素进行排序。
2.因为两个链表的长度可能不同，则将两链表相同长度的一部分进行排序，将较长链表的后边直接连接在排好序的链表后边

#include<stdio.h>
#include<stdlib.h> 
typedef struct Node
{
 int data;
 struct Node *next;
}Node;
Node* Hebing(Node* head1, Node* head2)  //合并两个有序链表成一个有序链表
{
 if(head1 == NULL)
  return head2;
 if(head2 == NULL)
  return head1;
 Node *head, *p1, *p2;
 if(head1->data < head2->data)   //确定好合并后的头结点 （从小到大） 
 {
  head = head1;
  p1 = head1->next;
  p2 = head2;
 }
 else{
  head = head2;
  p1 = head1;
  p2 = head2->next;
 } 
 Node *move = head;   //定义一个临时指针,(不用创建新链表占用空间)将两个链表连接在一起
 while(p1 && p2)      //p1,p2都不为空 
 {
  if(p1->data <= p2->data)
  {
   move->next = p1;
   move = p1;
   p1 = p1->next;
  }
  else
  {
   move->next = p2;
   move = p2;
   p2 = p2->next;
  }
 }
 if(p1)   //p1比p2长，比较完最小长度的链表节点后，因为有序，剩下的直接加到比较完的后边 
  move->next = p1;     // 补齐p1剩余未比较的节点
 if(p2)
  move->next = p2;     // 补齐p2剩余未比较的节点
 return head;
}
Node* Creat()      //链表的创建
{
 Node *head,*p,*s;
 head =(struct Node *)malloc(sizeof(struct Node));
 int x,flag = 1;
 if(head == NULL)
  printf("头结点创建失败!\n");
 p = head;   //p永远指向head的尾部 
 printf("输入(以0结束，从小到大):");
 while(flag)
 {
  scanf("%d",&x);
  if(x != 0)
  {
   s =(struct Node *)malloc(sizeof(struct Node));
   s->data = x;
   p->next = s;
   p = s; 
  }
  else
   flag = 0;  
 }
 head = head->next;
 p->next = NULL;
 printf("链表建立成功！\n"); 
    return head; 
}
void Print(Node *head)
{
 Node *p = head;
 while(p!=NULL)
 {
  printf("%d  ",p->data);
  p = p->next;
 }
 //printf("\n");
}
int main()
{
 Node *head1 = Creat();
 Node *head2 = Creat();
 Node *head3 = Hebing(head1, head2);
 Print(head3);
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92