《单链表合并为有序链表》由会员分享，可在线阅读，更多相关《单链表合并为有序链表（10页珍藏版）》请在金锄头文库上搜索。
1、1、 已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表仍然有序，要求用递归 方法实现。#include #include struct Nodeint num;Node *next;Node *Merge(Node *head1,Node *head2)if(head1=NULL)return head2;if(head2=NULL)return head1;Node *head=NULL;if(head1-numnum)head=head1;head-next=Merge(head1-next,head2);elsehead=head2;head-next=Merg
2、e(head1,head2-next);return head;2、递增有序的 2 个单链表合并成一个递增有序的单链表，不用任何库函数调用 /*题目描述: 2 个递增有序的单链表，请你把它两个合并成一个有序的单链表，分普通和不能用任何库函数 2 种方法作者: xiaocui时间: 2007.11.4版本: v1.0*/* 说明: 如果采用一般的做法，直接申请新的空间，组成一个新的单链表，直接进行归并就可以得到整体的有序序列，这个相对比较简单。如果不能用任何库函数，也就是不能利用 malloc 分配内存，就是要利用现有的 2 个链表，进行元素交换得到最后有序的链表。*/#include usin
3、g namespace std;/* 单链表节点 */struct nodeint value;node* next;/* 给单链表添加节点 */void insertNode(node* head, int value)node* p = head-next;if ( p = NULL )p = new node;p-value = value;p-next = NULL;head-next = p;return;while ( p-next != NULL )p = p-next;node* tmp = new node;tmp-value = value;tmp-next = NULL;
4、p-next = tmp;/* 遍历输出链表节点 */void print(node* head)node* p = head-next;while ( p != NULL )cout value next;cout next = NULL;node* p = headA-next;node* q = headB-next;if ( p = NULL )return headB;if ( q = NULL )return headA;while ( (p != NULL) & (q != NULL) )if ( p-value = q-value ) insertNode(head, p-va
5、lue);insertNode(head, q-value);p = p-next;q = q-next;else if ( p-value value )insertNode(head, p-value);p = p-next;else if ( p-value q-value )insertNode(head, q-value);q = q-next;while ( p != NULL )insertNode(head, p-value);p = p-next;while ( q != NULL )insertNode(head, q-value);q = q-next;return he
6、ad;/* 下面实现不使用任何库函数， 利用交换的方法在原空间实现整体有序。 方法是先确定哪一个链表的第一个节点的值小，把这个链表的头结点作为合并后链表的头结点，然后比较 2 个有序链表的当前节点的值，如果代表最后合并链表的值小，则不用交换，否则把两个值交换，最后合并链表始终保持两个值中的小值。另一个链表由于交换了一个元素，当前元素可能影响该链表的有序递增，对其进行调整使其保持递增有序，然后重复上述动作，直到一个链表遍历结束，然后把剩余的链表连接起来就行。*/* 调整链表的第一个节点，使其变成递增有序 */void chg2sort(node* head, node* &p)if (head-
7、next = NULL ) /没有节点，直接返回return;node* s = head;while ( s-next != p ) /s 指向 p 的前一个节点s = s-next;/下面的一段找到第一个大于 p 节点值的节点node* q = p;node* r = q;while ( q != NULL )if ( q-value value )r = q; /r 始终指向 q 的前一个节点q = q-next;elsebreak;/下面调整指针，其实可以统一写出来，为了阅读清晰把 q 为 NULL 和非 NULL 分开写出来if ( q = NULL )r-next = p;s-ne
8、xt = p-next;p-next = NULL;else if ( q != NULL )s-next = p-next;r-next = p;p-next = q;/由于链表进行了调换，当前链表指针也需要改变p = s-next;/* 两个有序链表进行合并 */node* merge(node* head1, node* head2)node* head; /合并后的头指针node* p = head1-next;node* q = head2-next;/有一个链表为空的情况，直接返回另一个链表if ( p = NULL )head = head2;return head;else i
9、f ( q = NULL )head = head1;return head;/两个都不为空,先确定哪个链表作为合并后的链表if ( (p != NULL) & (q != NULL) )if ( p-value value ) head = head1;elsehead = head2;node* p_prior; /始终指向 p 节点的前一个节点node* q_prior;while ( (p != NULL) & (q != NULL) )if ( p -value value )if ( head = head1 )p_prior = p;p = p-next;else if ( he
10、ad = head2 )/进行当前节点值的交换int tmp = p-value;p-value = q-value;q-value = tmp;chg2sort(head1, p); /交换元素后的调整q_prior = q;q = q-next;else if ( p-value = q-value )p_prior = p;p = p-next;q_prior = q; q = q-next;else if ( p-value q-value )if ( head = head1 )int tmp = p-value;p-value = q-value;q-value = tmp;chg
11、2sort(head2, q);p_prior = p;p = p-next;else if ( head = head2 )q_prior = q;q = q-next;if ( p != NULL )q_prior-next = p;if ( q != NULL )p_prior-next = q;return head;int main()/* 建立有序链表 A */int a5 = 1, 5, 8, 10, 20;node* headA = new node;headA-next = NULL;for (int i = 0; i next = NULL;for (int i = 0; i next = NULL;for (int i = 0; i next);print(headC);head = merge(headA, headB);print(head);return 0;
