18.[Linked list]:234. Palindrome Linked List

23. Merge k Sorted ListsHard17.3K624Companies

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.

Loading...LeetCode

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;
}