单链表交叉合并

谁借莪１个温暖的怀抱￠ 2023-02-17 08:49 4阅读 0赞

输入两个单链表，使其交叉合并形成一个单链表。  
如：1 3 5 7 9  
2 4 6 8 0  
合并后：1 2 3 4 5 6 7 8 9 0  
如果一个单链表比另一个长，则将多余部分加到后面。  
具体代码如下：

#include<stdio.h>
    //定义链表
    typedef struct node
    { 
    	int data;
    	struct node *next;
     }Node,*NodeP;
     //链表输入数据
     NodeP create1()
    { 
    	NodeP head=NULL,p,q;
     	char c;
     	int x;
    	while(1)
    	{ 
    		scanf("%d",&x);
    		p = new Node;
    		p->data = x;
    		p->next = NULL;
    		if(head==NULL)
    		{ 
    			head = q = p;
    		}
    		else
    		{ 
    			q->next = p;
    			q = p;
    		}
    		scanf("%c",&c);//控制结束时刻
    		if(c=='\n')
    			break;
    	}
    	return head;
    } 
    
     NodeP create2()
    { 
    	NodeP head=NULL,p,q;
     	int x;
    	while(scanf("%d",&x)==1)//学校测试数据是存储在文件中，所以用scanf("%d",&x)==1
    	{ 
    		p = new Node;
    		p->data = x;
    		p->next = NULL;
    		if(head==NULL)
    		{ 
    			head = q = p;
    		}
    		else
    		{ 
    			q->next = p;
    			q = p;
    		}
    	}
    	return head;
    } 
    //链表交叉合并
    void merge(NodeP head1, NodeP head2)
    { 
    	NodeP p1,p2,q1,q2,q;
    	p1 = head1;
    	p2 = head2;
    	q = head1;
    	while(p1 && p2)
    	{ 
    		q1 = p1->next;
    		q2 = p2->next;
    		p1->next = p2;
    		p2->next = q1;
    		q = p2;
    		p1 = q1;
    		p2 = q2;	
    	}
    	if(!p1 && p2)
    		q->next = p2;
    }
    //打印链表
    void print(NodeP head)
    { 
    	NodeP p=head;
    	while (p)
    	{ 
    		printf("%d ",p->data);
    		p = p->next;
    	}
    }
    
    int main()
    { 
    	NodeP head1,head2;
    	head1 = create1();
    	head2 = create2();
    	merge(head1,head2);
    	print(head1);
     }

由于新学链表，所以对于链表不大懂，只能粗略注释。。。