FilesExpand file tree

 master

/

MergekSortedLists.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

46 lines (41 loc) · 998 Bytes

 master

/

MergekSortedLists.java

Copy path

Top

File metadata and controls

• Code
• Blame

46 lines (41 loc) · 998 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

import java.util.ArrayList;

import java.util.Comparator;

import java.util.PriorityQueue;

/**

* Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

*

*/

public class MergekSortedLists {

public ListNode mergeKLists(ArrayList<ListNode> lists) {

if (lists == null || lists.isEmpty())

return null;

Comparator<ListNode> comp = new Comparator<ListNode>() {

public int compare(ListNode o1, ListNode o2) {

if (o1.val < o2.val)

return -1;

if (o1.val > o2.val)

return 1;

return 0;

}

};

PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(

lists.size(), comp);

for (ListNode node : lists) {

if (node != null)

heap.add(node);

}

ListNode head = null, cur = null;

while (!heap.isEmpty()) {

if (head == null) {

head = heap.poll();

cur = head;

} else {

cur.next = heap.poll();

cur = cur.next;

}

if (cur.next != null)

heap.add(cur.next);

}

return head;

}

}