You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.
With array
time: O(N)
space: O(N)
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
if (head === null) return true;
if (head.next === null) return true;
const arr = [];
let curr = head;
while (curr !== null) {
arr.push(curr.val);
curr = curr.next;
}
let left = 0;
let right = arr.length - 1;
while (left <= right) {
if (arr[left] !== arr[right]) return false;
left++;
right--;
}
return true;
};
With reversing array
time: O(N)
space: O(1)
var isPalindrome = function(head) {
if (head === null) return true;
if (head.next === null) return true;
let one = head;
let two = head;
while (two.next !== null && two.next.next !== null) {
one = one.next;
two = two.next.next;
}
// 1 2 3 => one is 1 => pivot should be 3
// 1 2 3 4 => one is 2 => pivot should be 3
// so one.next is pivot for odd and even
const pivot = one.next;
one = head;
two = reverse(pivot);
while (two !== null) {
if (two.val !== one.val) return false;
one = one.next;
two = two.next;
}
return true;
};
function reverse(node) {
let prev = null;
let curr = node;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
