LeetCode 23.Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
분석 및 답변:
K개의 질서정연한 체인 테이블을 병합합니다.앞에 두 개의 체인 테이블을 통합하는 프로그램이 있는 이상 이 문제는 분리법으로 풀 것이 틀림없다. 두 개의 합병은 바로 병합 정렬과 유사하고 복잡도는 O(n*logn)이다.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
queue<ListNode *> q;
ListNode *l1 = NULL, *l2 = NULL;
for (vector<ListNode *>::iterator itr = lists.begin();
itr != lists.end(); itr++) {
q.push(*itr);
}
while (!q.empty()) {
l1 = q.front();
q.pop();
if (q.empty())
break;
l2 = q.front();
q.pop();
q.push(mergeTwoLists(l1, l2));
}
return l1;
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *p, *result;
p = result = new ListNode(0); //
while (l1 || l2) {
if (l2 == NULL || (l1 && l2 && l1->val < l2->val)) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
return result->next;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[SwiftUI]List화한 CoreData를 가로 스와이프로 행 삭제하는 방법상당히 조사했지만 일본어 자료가 없었기 때문에 비망록으로 남겨 둔다. 아래와 같이 CoreData를 참조한 리스트를 가로 스와이프로 삭제하고 싶었다. UI 요소뿐만 아니라 원본 데이터 당 삭제합니다. 잘 다른 페이지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
