LeetCode 21-25

本篇记录 LeetCode 算法部分第 21 至 25 题。

Merge Two Sorted Lists

将两个有序链表合并成一个新的有序链表。

题目不复杂，取两个指针分别往下遍历两个链表的每个节点，逐次指向节点的值，取其较小值，并移动该指针，另一指针不动。继续往下比较，知道其中有一个指针到达末端为止。循环解法：

// MergeTwoSortedLists.java v1.0
// Definition for singly-linked list.
// public class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) { val = x; }
// }
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode temp = res;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        if (l1 == null) temp.next = l2;
        else temp.next = l1;
        return res.next;
    }
}

递归解法：

// MergeTwoSortedLists.java v1.1
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        pickListNode(l1, l2, res);
        return res.next;
    }

    private void pickListNode(ListNode l1, ListNode l2, ListNode res) {
        if (l1 == null || l2 == null) {
            res.next = l1 == null ? l2 : l1;
        } else if (l1.val < l2.val) {
            res.next = l1;
            l1 = l1.next;
            pickListNode(l1, l2, res.next);
        } else {
            res.next = l2;
            l2 = l2.next;
            pickListNode(l1, l2, res.next);
        }
    }
}

Status	Tests	Run Time	Language
Accepted	208 / 208	1 ms	Java

Generate Parentheses

第 22 题 Generate Parentheses

给定 n 对括号，编写方法生成所有可能的有效组合形式。例如，n = 3，所有的组合情况为：[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

这题很容易想起之前做过的第 20 题 Valid Parentheses，当时利用了栈的 FILO 特性去检验括号组合的有效性。一个很直接的想法就是枚举全部的组合，然后传给 Valid Parentheses 方法去做有效性检验。但是这种方法平方级的时间复杂度太高，因为要判断所有组合。 n + 1 对括号的组合，可以发现，其实就是将新增的一对括号和之前的 n 对括号的组合拼起来。因此这里就可以利用递归的思想。 n 对括号组合，就需要把 n 个 "(" 和 n 个 ")" 插入进字符串中。而且从左往右，"(" 的数量一定不少于 ")" 才能使得组合有效，换句话说，就是只有在待插入的 ")"的数量大于待插入的 "(" 数量时，才需要往字符串中插入 ")"。当待插入的括号数量为零时，结束递归，将所得括号字符串添加进列表里。

// GenerateParentheses.java
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if (n <= 0) return list;
        recursive(list, "", n, n);
        return list;
    }
    private void recursive(List<String> result, String paren, int left, int right) {
        if (left == 0 && right == 0) {
            result.add(paren);
            return;
        }
        if (left > 0) {
            recursive(result, paren + "(", left - 1, right);
        }
        if (right > 0 && left < right) {
            recursive(result, paren + ")", left, right - 1);
        }
    }
}

Status	Tests	Run Time	Language
Accepted	8 / 8	2 ms	Java

Merge k Sorted Lists

第 23 题 Merge k Sorted Lists

Swap Nodes in Pairs

第 24 题 Swap Nodes in Pairs

给定一个 Linked list，两两交换相邻节点，返回该链表。例如，给定的链表为 1 ->2 -> 3 -> 4，返回结果为 2 -> 1 -> 4 -> 3。

首先需要新建一个 ListNode 保存给定 ListNode 的头指针,这样在交换相邻节点时,该指针位置能保持固定不动。此外还需要另一个 ListNode 作为移动的指针来交换相邻节点，因此还需要创建两个临时的 ListNode，一左一右作交换。

// SwapNodesInPairs.java
public class Solution {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode swapPairs(ListNode head) {
        ListNode res = new ListNode(0);
        ListNode curNode = res;
        res.next = head;
        while (curNode.next != null && curNode.next.next != null) {
            ListNode l = curNode.next, r = curNode.next.next;
            curNode.next = r;
            l.next = r.next;
            r.next = l;
            curNode = l;
        }
        return res.next;
    }
}

Status	Tests	Run Time	Language
Accepted	55 / 55	0 ms	Java

Merge Reverse Nodes in k-Group

第 25 题 Reverse Nodes in k-Group

// MergeReverseNodesInKGroup.java