5，两个不交叉的有序链表的合并

系统管理员 2022-05-26 07:58 124阅读 0赞

思路：

比较大小，控制指针指向，如果一个链表已经结束，则把剩下的链表加上去即可。

注意：

要判断输入时候正确。

两个链表是否为空链表等特殊情况。

如果交叉了怎么办。后面会介绍。

// LinkTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    using namespace std;
    
    //链表的结构体
    struct node
    {
    	char val;
    	node * next;
    };
    
    //2，找第4个结点
    struct node * create( string & str_link )
    {
    	int len = str_link.length();
    
    	struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素
    	struct node * preNode = phead;
    	for( int i=0; i<len; i++ )
    	{
    		struct node * pNode = new node();
    		pNode->val = str_link[i];
    		pNode->next = NULL;
    		preNode->next = pNode;
    		preNode = pNode;
    	}
    	return phead;
    }
    
    void out_link( struct node * phead )
    {
    	if( phead == NULL )
    		return;
    	struct node * pNode = phead->next;
    	while( pNode )
    	{
    		cout <<pNode->val;
    		pNode = pNode->next;
    	}
    	cout << endl;
    }
    
    
    struct node * merge_link( struct node * phead1, struct node * phead2 )
    {
    	if( !phead1 || !phead1->next) return phead2;
    	if( !phead2 || !phead2->next) return phead1;
    
    	struct node * phead = phead1;
    	struct node * pNode = phead;
    	struct node * pNode1 = phead1->next;
    	struct node * pNode2 = phead2->next;
    	delete phead2;
    
    	while( pNode1 && pNode2)
    	{
    		if( pNode1->val <= pNode2->val )
    		{
    			pNode->next = pNode1;
    			pNode1 = pNode1->next;
    		}
    		else
    		{
    			pNode->next = pNode2;			
    			pNode2 = pNode2->next;
    		}
    		pNode = pNode->next;
    	}
    
    	if( pNode2 )
    		pNode->next = pNode2;
    
    	if( pNode1 )
    		pNode->next = pNode1;
    
    	return phead;
    }
    
    void test()
    {
    	string str;
    	cin >> str;
    	struct node *phead1 = create( str );
    	cin >> str;
    	struct node *phead2 = create( str );
    	
    	struct node * phead = merge_link( phead1, phead2 );
    	cout << "after merge: "<<endl;
    	out_link( phead );
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	test();
    	return 0;
    }