LeetCode(力扣)答案解析（五）

[Checkson]

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题解：

/**
 * 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) {
    var ans = new ListNode(null),
        curNode = ans;
    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            curNode.next = l1;
            l1 = l1.next;
        } else {
            curNode.next = l2;
            l2 = l2.next;
        }
        curNode = curNode.next;
    }
    curNode.next = (l1 !== null) ? l1 : l2;
    return ans.next;
};

解析：

这道题比较简单，思路大概用一个中间链表ans来存储结果，然后不断找出两个列表较小值，直到ans的末尾，不断重复这个步骤，直到l1或l2都遍历完，然后将没遍历完的l1或者l2接到ans后面。

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1：

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例2：

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

题解：

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var count = nums.length > 0 ? 1 : 0;
    for (var i = 1, len = nums.length; i < len; i++) {
        if (nums[count - 1] ^ nums[i]) { // 若不相同
            nums[count++] = nums[i];
        }
    }
    return count;
};

解析：

因为数组本来就有序的，首先我们要记录当前遍历位置一共有多少个不同的元素，我们用count表示，然后数组的前count个元素面要始终保持互不相同。这样，我们循环对比的时候，只需和第count - 1元素是否相等，若相等，继续寻找下一个不同的元素；若不相等，则将这个不同的数，替换在count位置。这样，count的值就是始终代表着原始数组中有多少个不同的值。

图解：

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

解析：

这道题，很简单。但是很多同学会有一个误区，就是真的会删除当前节点，步骤会变得繁琐。其实换种思路，将当前节点的值替换为下一个节点的值，然后删除下一个节点，问题就变得简单多了。