Skip to content

Latest commit

 

History

History
212 lines (188 loc) · 3.77 KB

21-40.md

File metadata and controls

212 lines (188 loc) · 3.77 KB

21. 合并两个有序链表

迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  let dummyHead = new ListNode()
  let ret = dummyHead
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      dummyHead.next = l1
      l1 = l1.next
    } else {
      dummyHead.next = l2
      l2 = l2.next
    }
    dummyHead = dummyHead.next
  }
  if (l1) {
    dummyHead.next = l1
  }
  if (l2) {
    dummyHead.next = l2
  }
  return ret.next
};

递归

var mergeTwoLists = function(l1, l2) {
  if (!l1) return l2
  if (!l2) return l1
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l2.next, l1)
    return l2
  }
}

22. 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

回溯（递归）

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  let result = []
  function trackback(s = '', left = 0, right = 0) {
    console.log('123:', s, left, right)
    if (s.length === 2 * n) {
      result.push(s)
    }
    if (left < n) {
      trackback(s + '(', left + 1, right)
    }
    if (right < left) {
      trackback(s + ')', left, right + 1)
    }
  }
  trackback()
  return result
};

23. 合并K个排序链表 (D)

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出:  1->1->2->3->4->4->5->6

分治

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  if (!l1) return l2
  if (!l2) return l1
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l2.next, l1)
    return l2
  }
}
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  const len = lists.length
  if (len === 0) return lists
  let interval = 1
  while (interval < len) {
    for (let i = 0; i < len - interval; i += interval * 2) {
      lists[i] = mergeTwoLists(lists[i], lists[i + interval])
    }
    interval *= 2
  }
  return lists[0]
}

24. 两两交换链表中的节点 (M)

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

参考： 画解算法：24. 两两交换链表中的节点

递归

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  if (!head || !head.next) return head
  const next = head.next
  head.next = swapPairs(next.next)
  next.next = head
  return next
}

非递归

var swapPairs = function(head) {
  const pre = new ListNode()
  pre.next = head
  let temp = pre
  let start, end
  while (temp.next && temp.next.next) {
    start = temp.next
    end = temp.next.next
    temp.next = end
    start.next = end.next
    end.next = start
    temp = start
  }
  return pre.next
};