论坛 › 数据结构与算法 › 数据结构

ljh11 发表于 2020-10-19 21:22:30

数据结构

将两个非递减的有序链表合并为一个非递增的有序链表，如何用C代码实现？
要求使用原来两个链表的存储空间

xieglt 发表于 2020-10-20 13:46:05

#include "stdio.h"
#include "stdlib.h"

typedef struct tagLinkList
{
        int data;
        struct tagLinkList * pNext;
}LL,*LPLL;

LPLL AddNode(int data)
{
        LPLL lpNode = (LPLL)malloc(sizeof(LL));
        lpNode->data = data;
        lpNode->pNext = NULL;
        return lpNode;
}

void DestoryList(LPLL head)
{
        while(head != NULL)
        {
                LPLL pNode = head;
                head = head->pNext;
                free(pNode);
        }
}

void DisplayList(LPLL head)
{
        while(head != NULL)
        {
                printf("%d,",head->data);
                head = head->pNext;
        }

        printf("\n");
}

LPLL MergeList(LPLL l1,LPLL l2)
{
        if(l1 == NULL)
        {
                return l2;
        }
       
        if(l2 == NULL)
        {
                return l1;
        }
       
        LPLL lpHead = (l1->data < l2->data) ? l1 : l2;
        LPLL lpBig = (l1->data < l2->data) ? l2 : l1;
       
        LPLL lpSmall = lpHead;
       
        while(lpSmall != NULL)
        {
                if(lpSmall->pNext == NULL)
                {
                        lpSmall->pNext = lpBig;
                        break;
                }
               
                if(lpSmall->pNext->data < lpBig->data)
                {
                        lpSmall = lpSmall->pNext;
                }
                else
                {
                        LPLL lpNode = lpSmall->pNext;
                        lpSmall->pNext = lpBig;
                       
                        lpSmall = lpBig;
                        lpBig = lpNode;
                }
        }       

        return lpHead;
}

int main()
{
        int i = 0;
        LPLL pList1 = NULL;
        LPLL pList2 = NULL;
        LPLL pTail = NULL;

        for(i = 5 ; i <= 20 ; i ++)
        {
                if(pList1 == NULL)
                {
                        pList1 = AddNode(i * 2);
                        pTail = pList1;
                }
                else
                {
                        pTail->pNext = AddNode(i * 2);
                        pTail = pTail->pNext;
                }
        }

        for(i = 1 ; i <= 10 ; i ++)
        {
                if(pList2 == NULL)
                {
                        pList2 = AddNode(i * 3);
                        pTail = pList2;
                }
                else
                {
                        pTail->pNext = AddNode(i * 3);
                        pTail = pTail->pNext;
                }
        }
       
        DisplayList(pList1);
        DisplayList(pList2);

        pList1 = MergeList(pList1,pList2);

        DisplayList(pList1);
        DestoryList(pList1);
       
      return 0;
}

ljh11 发表于 2020-10-20 14:54:53

数据结构的相关作业，有没有简单点的

查看完整版本: 数据结构