内容发布更新时间 : 2024/12/24 3:10:57星期一 下面是文章的全部内容请认真阅读。

//已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。（递归方法） Node *MergeRecursive(Node *head1 , Node *head2) {

if ( head1 == NULL ) return head2 ; if ( head2 == NULL) return head1 ; Node *head = NULL ;

if ( head1->num < head2->num ) {

head = head1 ;

head->next = MergeRecursive(head1->next,head2); } else {

head = head2 ;

head->next = MergeRecursive(head1,head2->next); }

return head ; }

从递归函数的定义不难看出，这个函数定义中递归调用时形参发生改变，即是当前节点的下一个节点，每一次递归都按照这个规律逐次遍历两个有序链表的每一个节点，判断大小后使head指向数据域较小的节点，由堆栈空间的思想可知递归到最后指向NULL时才返回两个链表的某一个头节点，而此时head->next=head2，head=head1链表的最后一个节点，该语句就使得这样一个指向关系确立起来。

以上均通过理想的有序链表，即链表1的任何一个数据值都小于链表2来做分析，其他的情况讨论方式类似。

Node* Delete(Node* head , int num) //删除节点 {

if (head==NULL) {

cout<<\<

Node *p1,*p2; p1=head;

while (p1->num!=num && p1->next) {

p2=p1; p1=p1->next; }

if (p1->num==num) {

if (p1==head)

{

head=p1->next; } else

p2->next=p1->next; } else

cout<<\<

Node* Insert(Node* head , int num) //插入节点 {

Node *p0,*p1,*p2; p1=head; p0=new Node; p0->num=num; if (head==NULL) {

head=p0;

p0->next=NULL; return head; }

while (p1->numnum && p1->next) {

p2=p1; p1=p1->next; }

if (p1->num>=p0->num) {if (p1==head) head=p0; else

p2->next=p0; p0->next=p1; } else {

p1->next=p0; p0->next=NULL; }

return head; }

void main() {省略不写}