>  기사  >  백엔드 개발  >  C 언어에서 두 개의 순서가 지정된 연결 목록을 병합하는 방법

C 언어에서 두 개의 순서가 지정된 연결 목록을 병합하는 방법

王林
王林원래의
2020-10-29 11:35:436706검색

C 언어에서 두 개의 순서 연결 목록을 병합하는 방법: 지정된 두 순서 연결 목록의 모든 노드를 연결하기만 하면 됩니다. 예를 들어 두 개의 순서 연결 리스트는 [1->2->4]와 [1->3->4]이고 병합된 순서 연결 리스트는 [1->1->2입니다. ->3->4->4].

C 언어에서 두 개의 순서가 지정된 연결 목록을 병합하는 방법

특정 방법:

두 개의 정렬된 연결 목록을 새로운 정렬된 연결 목록으로 병합하고 반환합니다. 새로운 연결리스트는 주어진 두 연결리스트의 모든 노드를 연결하여 형성됩니다.

(추천 비디오 튜토리얼: java 강좌)

입력:

1->2->4, 1->3->4

출력:

1->1->2->3->4->4

분석: 두 개의 연결된 목록은 순서가 지정된 연결 목록이므로 두 개의 연결된 목록을 순회하여 크기를 비교하면 됩니다.

코드 구현:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL){
        return l2;
    }
    if(l2==NULL){
        return l1;
    }
    struct ListNode *l = (struct ListNode*)malloc(sizeof(struct ListNode));
    l->next = NULL;
    struct ListNode *list1 = l1;
    struct ListNode *list2 = l2;
    if(l1->val<l2->val){
        l->val=l1->val;
        if(list1->next==NULL){
            l->next=list2;
            return l;
        }
        list1=list1->next;
    }else{
        l->val=l2->val;
        if(list2->next==NULL){
            l->next=list1;
            return l;
        }
        list2=list2->next;
    }
    struct ListNode *list = l;
    while(list1->next!=NULL&&list2->next!=NULL){
        if(list1->val<=list2->val){
            struct ListNode *body = (struct ListNode *)malloc(sizeof(struct ListNode));
            body->val = list1->val;
            body->next = NULL;
            list->next = body;
            list = list->next;
            list1 = list1->next;
        }else{
            struct ListNode *body = (struct ListNode*)malloc(sizeof(struct ListNode));
            body->val=list2->val;
            body->next=NULL;
            list->next=body;
            list=list->next;
            list2=list2->next;
        }
    }
    if(list1->next==NULL){
        while(list2->next!=NULL){
            if(list1->val<=list2->val){
                list->next = list1;
                list = list->next;
                list->next=list2;
                return l;
            }else{
                struct ListNode *body = (struct ListNode*)malloc(sizeof(struct ListNode));
                body->val=list2->val;
                body->next=NULL;
                list->next=body;
                list=list->next;
                list2=list2->next;
            }
        }
    }else{
        while(list1->next!=NULL){
            if(list2->val<=list1->val){
                list->next=list2;
                list=list->next;
                list->next=list1;
                return l;
            }else{
                struct ListNode *body = (struct ListNode*)malloc(sizeof(struct ListNode));
                body->val=list1->val;
                body->next=NULL;
                list->next=body;
                list=list->next;
                list1=list1->next;
            }
        }
    }
    if(list1->next==NULL&&list2->next==NULL){
        if(list1->val<=list2->val){
            list->next = list1;
            list=list->next;
            list->next=list2;
        }else{
            list->next=list2;
            list=list->next;
            list->next=list1;
        }
    }



    return l;
}

그림 및 텍스트 튜토리얼 공유: Java 시작하기

위 내용은 C 언어에서 두 개의 순서가 지정된 연결 목록을 병합하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.