LeetCode 탐색 의 여행 (7)

1583 단어 코드 트 레이 닝
겨울방학 이 끝나 고 오늘부터 학습 상태 에 들 어 갑 니 다. 지금 은 Leet Code 21 문제 까지 두 개의 질서 있 는 링크 를 합병 합 니 다. 이것 은 데이터 구조 에 필수 적 인 문제 일 것 입 니 다.
분석: 이 문 제 는 간단 하지만 판단 조건 이 비교적 많 기 때문에 주도면밀 하 게 고려 해 야 한다.먼저 두 개의 입력 링크 가 비어 있 는 지 여 부 를 판단 하고 모두 비어 있 으 면 빈 지침 으로 돌아 가 고 그 중 하 나 는 비어 있 으 면 다른 하 나 를 되 돌려 줍 니 다.그 다음 에 처음부터 두 개의 링크 를 옮 겨 다 니 며 크기 를 비교 하고 어느 것 이 작 으 면 새로운 링크 꼬리 에 연결 되 고 한 개의 링크 가 비어 있 을 때 까지 뒤로 이동 합 니 다.마지막 으로 어떤 링크 가 먼저 비어 있 는 지 판단 하면 링크 의 나머지 꼬리 부분 을 새로운 링크 의 꼬리 부분 에 연결 시 키 고 마지막 으로 새로운 링크 의 머리 를 출력 합 니 다.
문제: 1. 여러 가지 상황 을 고려 하여 비어 있 습 니 다.2. 시간 효율 이 매우 낮 습 니 다. 이것 은 이해 하지 못 했 습 니 다. 다른 사람들 이 사용 하 는 재 귀 는 시간 을 줄 일 수 있 고 최적화 할 수 있 습 니 다.
코드 첨부:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL&&l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *head=new ListNode(0);
        ListNode *r=head;
        while(l1&&l2)
        {
            if(l1->val>l2->val)
            {
                r->next=l2;
                l2=l2->next;
            }
            else
            {
                r->next=l1;
                l1=l1->next;
            }
            r=r->next;
        }
        if(l1)
            r->next=l1;
        if(l2)
            r->next=l2;
        return head->next;
        
    }
};

좋은 웹페이지 즐겨찾기