23.Merge-k-Sorted-Lists.md

23. Merge k Sorted Lists

---

题目地址

https://leetcode.com/problems/merge-k-sorted-lists/

https://www.lintcode.com/problem/merge-k-sorted-lists/description

题目描述

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

Example:
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6 Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

代码

Approach 1: Divide & Conquer

class Solution {
  public ListNode mergeKLists(List<ListNode> lists) {
    if (lists.size() == 0) return null;

    return mergeHelper(lists, 0, lists.size() - 1);
  }

  private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
    if (start == end) return lists.get(start);

    int mid = start + (end - start) / 2;
    ListNode left = mergeHelper(lists, start, mid);
    ListNode right = mergeHelper(lists, mid + 1, end);
    return mergeTwoLists(left, right);
  }

  private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (list1 != null && list2 != null) {
      if (list1.val < list2.val) {
        tail.next = list1;
        tail = list1;
        list1 = list1.next;
      } else {
        tail.next = list2;
        tail = list2;
        list2 = list2.next;
      }
    }

    if (list1 != null) {
      tail.next = list1;
    } else {
      tail.next = list2;
    }

      return dummy.next;
  }
}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
        return partition(lists, 0, lists.length - 1);
    }
    
    private ListNode partition(ListNode[] lists, int start, int end) {
        if (start == end)   return lists[start];
        if (start < end) {
            int mid = start + (end - start) / 2;
            ListNode node1 = partition(lists, start, mid);
            ListNode node2 = partition(lists, mid + 1, end);
            return merge(node1, node2);
        } else {
            return null;
        }
    }
    
    private ListNode merge(ListNode node1, ListNode node2) {
        if (node1 == null)  return node2;
        if (node2 == null)  return node1;
        
        if (node1.val < node2.val) {
            node1.next = merge(node1.next, node2);
            return node1;
        } else {
            node2.next = merge(node1, node2.next);
            return node2;
        }
    }
}

Approach 2: PriorityQueue

class Solution {
  public ListNode mergeKLists(List<ListNode> lists) {
    if (lists == null || lists.size() == 0) return null;

    Queue<ListNode> heap = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
    for (int i = 0; i < lists.size(); i++) {
        if (lists.get(i) != null) {
            heap.add(lists.get(i));
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode head = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        head.next = node;
        head = node;
        if (node != null) {
            heap.add(node.next);
        }
    }

    return dummy.next;
  }
}

Approach 3: Merge two by two

class Soluution {
  public ListNode mergeKLists(List<ListNode> Lists) {
    if (lists == null || lists.size() == 0)    return null;

    while (lsits.size() > 1) {
      List<ListNode> new_lists = new ArrayList<ListNode>();
      for (int i = 0; i + 1 < lists.size(); i += 2) {
        ListNode merged_list = merge(lists.get(i), lists.get(i + 1));
        new_lists.add(merged_list);
      }
      if (lists.size() % 2 == 1) {
        new_lists.add(lists.get(lists.size() - 1));
      }
      lists = new_lists;
    }

    return lists.get(0);
  }

  private ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
      if (a.val < b.val) {
        tail.next = a;
        a = a.next;
      } else {
        tail.next = b;
        b = b.next;
      }
      tail = tail.next;
    }

    if (a != null) {
      tail.next = a;
    } else {
      tail.next = b;
    }

    return dummy.next;
  }

}

Approach 5: Brute Force

Intuition

• Traverse all the linked lists and collect the values of the nodes into an array.
• Sort and iterate over this array to get the proper value of nodes.
• Create a new sorted linked list and extend it with the new nodes.
• Time complexity : O_(_N_log_N) where N is the total number of nodes.
  • Collecting all the values costs O_(_N) time.
  • A stable sorting algorithm costs O_(_N_log_N) time.
  • Iterating for creating the linked list costs O_(_N) time.
• Space complexity : O(N).
  • Sorting cost O(N) space (depends on the algorithm you choose).
  • Creating a new linked list costs O(N) space.

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];
            while (node != null) {
                list.add(node.val);
                node = node.next;
            }
        }

        ListNode dummy = new ListNode(0);
        /// sort list and append to the dummy

    return dummy;
  }
}