{"action":"created","comment":{"url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/comments/104282578","pull_request_review_id":25114685,"id":104282578,"diff_hunk":"@@ -0,0 +1,17 @@\n+##题目分析\n+\n+给定k个有序链表，求出一个合并以后的有序链表。\n+\n+###题解思路（1）\n+\n+首先我们可以确定一个复杂度上界，就是把这k个链表中的所有节点保存下来排序，这样的做法复杂度主要在排序，是一个`O(nlgn)`的做法。\n+\n+###题解思路（2）\n+\n+接下用k个链表本身已经有序这个限制来优化下上界的算法。假设有两个来自同一个链表的元素`a,b（a<b）`，然后我们要归并到一个目标链表，那么在`a`没有被放进目标链表之前`b`肯定不会被放进目标链表。所以目标链表每次放进去的元素必然是k个链表当前表头元素中的最小值。所以我们需要维护一个数据结构，这个数据结构需要支持：\n+\n++ 能快速查找k个元素的最小值；\n++ 支持插入，删除最小元素。\n+\n+这些基本的操作几乎所有的平衡树都能完成。但是用平衡树解决有点大材小用了，这些要求我们可以用一个堆又快（常数小）又好（编程复杂度低）的实现，比如在C++中堆就封装成了priority_queue,可以直接拿来用。于是我们就实现了一个`O(nlgk)`的算法，优于简单无脑的上界算法。","path":"23-mergeKLists/README.md","position":16,"original_position":16,"commit_id":"ab744b57029e14507e8651b7b8263dbbca3b51a0","original_commit_id":"ab744b57029e14507e8651b7b8263dbbca3b51a0","user":{"login":"yizhen20133868","id":20279325,"avatar_url":"https://avatars1.githubusercontent.com/u/20279325?v=3","gravatar_id":"","url":"https://api.github.com/users/yizhen20133868","html_url":"https://github.com/yizhen20133868","followers_url":"https://api.github.com/users/yizhen20133868/followers","following_url":"https://api.github.com/users/yizhen20133868/following{/other_user}","gists_url":"https://api.github.com/users/yizhen20133868/gists{/gist_id}","starred_url":"https://api.github.com/users/yizhen20133868/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yizhen20133868/subscriptions","organizations_url":"https://api.github.com/users/yizhen20133868/orgs","repos_url":"https://api.github.com/users/yizhen20133868/repos","events_url":"https://api.github.com/users/yizhen20133868/events{/privacy}","received_events_url":"https://api.github.com/users/yizhen20133868/received_events","type":"User","site_admin":false},"body":"小茅，简单解释一下为什么这样就是实现了一个0(nlgk)算法的复杂度？ @morejarphone ","created_at":"2017-03-04T07:51:35Z","updated_at":"2017-03-04T07:51:40Z","html_url":"https://github.com/Leetcode-Tutorial/Tutorial/pull/16#discussion_r104282578","pull_request_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16","_links":{"self":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/comments/104282578"},"html":{"href":"https://github.com/Leetcode-Tutorial/Tutorial/pull/16#discussion_r104282578"},"pull_request":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16"}}},"pull_request":{"url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16","id":108907263,"html_url":"https://github.com/Leetcode-Tutorial/Tutorial/pull/16","diff_url":"https://github.com/Leetcode-Tutorial/Tutorial/pull/16.diff","patch_url":"https://github.com/Leetcode-Tutorial/Tutorial/pull/16.patch","issue_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/16","number":16,"state":"open","locked":false,"title":"solution for 23, 32","user":{"login":"morejarphone","id":19873277,"avatar_url":"https://avatars2.githubusercontent.com/u/19873277?v=3","gravatar_id":"","url":"https://api.github.com/users/morejarphone","html_url":"https://github.com/morejarphone","followers_url":"https://api.github.com/users/morejarphone/followers","following_url":"https://api.github.com/users/morejarphone/following{/other_user}","gists_url":"https://api.github.com/users/morejarphone/gists{/gist_id}","starred_url":"https://api.github.com/users/morejarphone/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/morejarphone/subscriptions","organizations_url":"https://api.github.com/users/morejarphone/orgs","repos_url":"https://api.github.com/users/morejarphone/repos","events_url":"https://api.github.com/users/morejarphone/events{/privacy}","received_events_url":"https://api.github.com/users/morejarphone/received_events","type":"User","site_admin":false},"body":"rt","created_at":"2017-03-03T04:53:52Z","updated_at":"2017-03-04T07:51:40Z","closed_at":null,"merged_at":null,"merge_commit_sha":"401ce31a9740ac0246b5f7fb62515471badce9fe","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16/commits","review_comments_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16/comments","review_comment_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/comments{/number}","comments_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/16/comments","statuses_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/statuses/ab744b57029e14507e8651b7b8263dbbca3b51a0","head":{"label":"Leetcode-Tutorial:morejarphone","ref":"morejarphone","sha":"ab744b57029e14507e8651b7b8263dbbca3b51a0","user":{"login":"Leetcode-Tutorial","id":25873768,"avatar_url":"https://avatars2.githubusercontent.com/u/25873768?v=3","gravatar_id":"","url":"https://api.github.com/users/Leetcode-Tutorial","html_url":"https://github.com/Leetcode-Tutorial","followers_url":"https://api.github.com/users/Leetcode-Tutorial/followers","following_url":"https://api.github.com/users/Leetcode-Tutorial/following{/other_user}","gists_url":"https://api.github.com/users/Leetcode-Tutorial/gists{/gist_id}","starred_url":"https://api.github.com/users/Leetcode-Tutorial/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Leetcode-Tutorial/subscriptions","organizations_url":"https://api.github.com/users/Leetcode-Tutorial/orgs","repos_url":"https://api.github.com/users/Leetcode-Tutorial/repos","events_url":"https://api.github.com/users/Leetcode-Tutorial/events{/privacy}","received_events_url":"https://api.github.com/users/Leetcode-Tutorial/received_events","type":"Organization","site_admin":false},"repo":{"id":82430027,"name":"Tutorial","full_name":"Leetcode-Tutorial/Tutorial","owner":{"login":"Leetcode-Tutorial","id":25873768,"avatar_url":"https://avatars2.githubusercontent.com/u/25873768?v=3","gravatar_id":"","url":"https://api.github.com/users/Leetcode-Tutorial","html_url":"https://github.com/Leetcode-Tutorial","followers_url":"https://api.github.com/users/Leetcode-Tutorial/followers","following_url":"https://api.github.com/users/Leetcode-Tutorial/following{/other_user}","gists_url":"https://api.github.com/users/Leetcode-Tutorial/gists{/gist_id}","starred_url":"https://api.github.com/users/Leetcode-Tutorial/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Leetcode-Tutorial/subscriptions","organizations_url":"https://api.github.com/users/Leetcode-Tutorial/orgs","repos_url":"https://api.github.com/users/Leetcode-Tutorial/repos","events_url":"https://api.github.com/users/Leetcode-Tutorial/events{/privacy}","received_events_url":"https://api.github.com/users/Leetcode-Tutorial/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/Leetcode-Tutorial/Tutorial","description":null,"fork":false,"url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial","forks_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/forks","keys_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/teams","hooks_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/hooks","issue_events_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/events{/number}","events_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/events","assignees_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/assignees{/user}","branches_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/branches{/branch}","tags_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/tags","blobs_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/refs{/sha}","trees_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/statuses/{sha}","languages_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/languages","stargazers_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/stargazers","contributors_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/contributors","subscribers_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/subscribers","subscription_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/subscription","commits_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/commits{/sha}","git_commits_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/commits{/sha}","comments_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/comments{/number}","issue_comment_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/comments{/number}","contents_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/contents/{+path}","compare_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/merges","archive_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/downloads","issues_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues{/number}","pulls_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls{/number}","milestones_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/milestones{/number}","notifications_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/labels{/name}","releases_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/releases{/id}","deployments_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/deployments","created_at":"2017-02-19T02:31:08Z","updated_at":"2017-02-22T05:53:13Z","pushed_at":"2017-03-04T07:51:13Z","git_url":"git://github.com/Leetcode-Tutorial/Tutorial.git","ssh_url":"git@github.com:Leetcode-Tutorial/Tutorial.git","clone_url":"https://github.com/Leetcode-Tutorial/Tutorial.git","svn_url":"https://github.com/Leetcode-Tutorial/Tutorial","homepage":null,"size":42,"stargazers_count":2,"watchers_count":2,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":7,"mirror_url":null,"open_issues_count":20,"forks":7,"open_issues":20,"watchers":2,"default_branch":"master"}},"base":{"label":"Leetcode-Tutorial:master","ref":"master","sha":"e7257823baf70690dd26f3c7e68a4f5adcb58207","user":{"login":"Leetcode-Tutorial","id":25873768,"avatar_url":"https://avatars2.githubusercontent.com/u/25873768?v=3","gravatar_id":"","url":"https://api.github.com/users/Leetcode-Tutorial","html_url":"https://github.com/Leetcode-Tutorial","followers_url":"https://api.github.com/users/Leetcode-Tutorial/followers","following_url":"https://api.github.com/users/Leetcode-Tutorial/following{/other_user}","gists_url":"https://api.github.com/users/Leetcode-Tutorial/gists{/gist_id}","starred_url":"https://api.github.com/users/Leetcode-Tutorial/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Leetcode-Tutorial/subscriptions","organizations_url":"https://api.github.com/users/Leetcode-Tutorial/orgs","repos_url":"https://api.github.com/users/Leetcode-Tutorial/repos","events_url":"https://api.github.com/users/Leetcode-Tutorial/events{/privacy}","received_events_url":"https://api.github.com/users/Leetcode-Tutorial/received_events","type":"Organization","site_admin":false},"repo":{"id":82430027,"name":"Tutorial","full_name":"Leetcode-Tutorial/Tutorial","owner":{"login":"Leetcode-Tutorial","id":25873768,"avatar_url":"https://avatars2.githubusercontent.com/u/25873768?v=3","gravatar_id":"","url":"https://api.github.com/users/Leetcode-Tutorial","html_url":"https://github.com/Leetcode-Tutorial","followers_url":"https://api.github.com/users/Leetcode-Tutorial/followers","following_url":"https://api.github.com/users/Leetcode-Tutorial/following{/other_user}","gists_url":"https://api.github.com/users/Leetcode-Tutorial/gists{/gist_id}","starred_url":"https://api.github.com/users/Leetcode-Tutorial/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Leetcode-Tutorial/subscriptions","organizations_url":"https://api.github.com/users/Leetcode-Tutorial/orgs","repos_url":"https://api.github.com/users/Leetcode-Tutorial/repos","events_url":"https://api.github.com/users/Leetcode-Tutorial/events{/privacy}","received_events_url":"https://api.github.com/users/Leetcode-Tutorial/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/Leetcode-Tutorial/Tutorial","description":null,"fork":false,"url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial","forks_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/forks","keys_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/teams","hooks_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/hooks","issue_events_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/events{/number}","events_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/events","assignees_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/assignees{/user}","branches_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/branches{/branch}","tags_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/tags","blobs_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/refs{/sha}","trees_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/statuses/{sha}","languages_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/languages","stargazers_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/stargazers","contributors_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/contributors","subscribers_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/subscribers","subscription_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/subscription","commits_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/commits{/sha}","git_commits_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/git/commits{/sha}","comments_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/comments{/number}","issue_comment_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/comments{/number}","contents_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/contents/{+path}","compare_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/merges","archive_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/downloads","issues_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues{/number}","pulls_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls{/number}","milestones_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/milestones{/number}","notifications_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/labels{/name}","releases_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/releases{/id}","deployments_url":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/deployments","created_at":"2017-02-19T02:31:08Z","updated_at":"2017-02-22T05:53:13Z","pushed_at":"2017-03-04T07:51:13Z","git_url":"git://github.com/Leetcode-Tutorial/Tutorial.git","ssh_url":"git@github.com:Leetcode-Tutorial/Tutorial.git","clone_url":"https://github.com/Leetcode-Tutorial/Tutorial.git","svn_url":"https://github.com/Leetcode-Tutorial/Tutorial","homepage":null,"size":42,"stargazers_count":2,"watchers_count":2,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":7,"mirror_url":null,"open_issues_count":20,"forks":7,"open_issues":20,"watchers":2,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16"},"html":{"href":"https://github.com/Leetcode-Tutorial/Tutorial/pull/16"},"issue":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/16"},"comments":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/issues/16/comments"},"review_comments":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16/comments"},"review_comment":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/pulls/16/commits"},"statuses":{"href":"https://api.github.com/repos/Leetcode-Tutorial/Tutorial/statuses/ab744b57029e14507e8651b7b8263dbbca3b51a0"}}}}
{"actor":{"display_login":"yizhen20133868"}}