C++LeetCode 구현(21.혼합 질서 있 는 링크 삽입)

[LeetCode]21.Merge Two Sorted Lists 를 혼합 하여 질서 있 는 링크 를 삽입 합 니 다.
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
이 혼합 삽입 질서 있 는 링크 는 내 가 이전에 혼합 삽입 질서 있 는 배열 과 매우 비슷 하 다.  Merge Sorted Array데이터 구조 가 배열 에서 링크 로 바 뀌 었 을 뿐 코드 는 오히려 간결 하 다.구체 적 인 사상 은 하나의 링크 를 새로 만 든 다음 에 두 개의 링크 중의 요소 수 치 를 비교 하고 작은 체인 을 새로운 링크 에 넣 는 것 이다.두 개의 입력 링크 의 길이 가 다 를 수 있 기 때문에 최종 적 으로 하나의 링크 가 모든 요 소 를 먼저 삽입 하면 다른 미 완성 링크 가 새로운 링크 의 끝 에 직접 연결된다.코드 는 다음 과 같 습 니 다:
C++해법 1:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

자바 해법 1:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1), cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

다음은 재 귀적 인 쓰기 방법 을 살 펴 보 겠 습 니 다.어떤 링크 가 비어 있 으 면 다른 것 으로 돌아 갑 니 다.그 다음 에 핵심 은 현재 두 노드 의 값 크기 를 비교 합 니 다.l1 이 작 으 면 l1 의 다음 노드 와 l2 에 대해 재 귀 함 수 를 호출 하고 반환 값 을 l1.next 에 부여 한 다음 에 l1 로 되 돌려 줍 니 다.그렇지 않 으 면 l2 의 다음 노드 와 l1 에 대해 재 귀 함 수 를 호출 하고 반환 값 을 l2.next 에 부여 한 다음 에 l2 로 돌아 갑 니 다.코드 는 다음 과 같 습 니 다.
C++해법 2:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

자바 해법 2:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

아래 의 이러한 재 귀적 인 문법 은 if 종문 을 없 애고 더욱 간결 해 보이 지만 사고방식 은 다 르 지 않다.
C++해법 3:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        ListNode *head = l1->val < l2->val ? l1 : l2;
        ListNode *nonhead = l1->val < l2->val ? l2 : l1;
        head->next = mergeTwoLists(head->next, nonhead);
        return head;
    }
};

자바 해법 3:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = (l1.val < l2.val) ? l1 : l2;
        ListNode nonhead = (l1.val < l2.val) ? l2 : l1;
        head.next = mergeTwoLists(head.next, nonhead);
        return head;
    }
}

 우 리 는 아직 세 줄 로 해결 할 수 있 으 니,정말 미 친 듯 이 나무 가 있다!
C++해법 4:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1 || (l2 && l1->val > l2->val)) swap(l1, l2);
        if (l1) l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
};

자바 해법 4:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || (l2 != null && l1.val > l2.val)) {
            ListNode t = l1; l1 = l2; l2 = t;
        }
        if (l1 != null) l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
}

여기 서 C++구현 LeetCode(21.혼합 삽입 질서 있 는 링크)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++혼합 삽입 질서 있 는 링크 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!