tìm tất cả cặp tổng k

const N = 5000;
const k = 10000;

// random array
const arr = Array.from({ length: N }, () => Math.floor(Math.random() * 10000));

// ==== Doubly Linked List ====
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(val) {
    const node = new Node(val);
    if (!this.head) {
      this.head = this.tail = node;
      return;
    }
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }
}

const dll = new DoublyLinkedList();
arr.forEach(v => dll.append(v));

function split(head) {
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let second = slow.next;
  slow.next = null;
  if (second) second.prev = null;
  return second;
}

function merge(a, b) {
  if (!a) return b;
  if (!b) return a;

  if (a.val < b.val) {
    a.next = merge(a.next, b);
    if (a.next) a.next.prev = a;
    a.prev = null;
    return a;
  } else {
    b.next = merge(a, b.next);
    if (b.next) b.next.prev = b;
    b.prev = null;
    return b;
  }
}

function mergeSort(head) {
  if (!head || !head.next) return head;
  let second = split(head);
  head = mergeSort(head);
  second = mergeSort(second);
  return merge(head, second);
}