单链表的排序与归并

单链表的排序与合并

输入两个链表，将各链表排序，然后将其合并成一个链表。

1、链表结构

typedef struct Node
{
	int data;
	struct Node *next;
}Node, *LinkList;

2、链表排序

//链表排序，由小到大
void sortLinkList(LinkList L)
{
	Node * R;		//前部已排序链表遍历指针
	Node * P;		//整个链表遍历指针
	Node * T;		//临时替换指针

	R= L;
	P = L->next;

	while(P != NULL  && P->next != NULL)
	{
		if(P->next->data < P->data)
		{
			R = L;
			while(R != P)
			{
				if(R->next->data > P->next->data)
				{
					T = P->next;
					P->next = T->next;
					T->next = R->next;
					R->next = T;

					break;
				}
				else
				{
					R = R->next;
				}
			}
		}
		else
		{
			P = P->next;
		}
	}
}

3、有序链表的合并

//有序链表A，B合到A
void mergerLinkList(LinkList A, LinkList B)
{
    Node *LA = A->next;
    Node *LB = B->next;
    Node *LR = A;

    while(LA != NULL && LB != NULL)
    {

    if(LA->data <= LB->data)
    {
        LR->next = LA;
        LR = LR->next;
        LA = LA->next;
    }
    else
    {
        LR->next = LB;
        LR = LR->next;
        LB = LB->next;
    }

    }

    if(LA)
    {
        LR->next = LA;
    }
    else
    {
        LR->next = LB;
    }
}

//～END~