每日5题Day5 - LeetCode 21 - 25

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：21. 合并两个有序链表 - 力扣（LeetCode）

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //讨论特殊情况
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //头节点
        ListNode node;
        if (list1.val <= list2.val) {
            node = new ListNode(list1.val);
            list1 = list1.next;
        } else {
            node = new ListNode(list2.val);
            list2 = list2.next;
        }
        //给一个dummy，用来最后定位
        ListNode dummy = new ListNode(-1, node);
        while (list1 != null || list2 != null) {
            //分类讨论
            ListNode curnode;
            if (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    curnode = new ListNode(list1.val);
                    list1 = list1.next;
                } else {
                    curnode = new ListNode(list2.val);
                    list2 = list2.next;
                }
            }
            else{
                if(list1 != null){
                    curnode = new ListNode(list1.val);
                    list1 = list1.next;
                }
                else{
                    curnode = new ListNode(list2.val);
                    list2 = list2.next;
                }
            }
            node.next = curnode;
            node = node.next;
        }
        return dummy.next;
    }
}

上面的代码用了太多的额外空间了，如果考虑使用递归呢？

如果对于链表（树的节点同样如此）使用递归的话，专注于每一个具体节点的行为，我们可以发现当list1为空的时候返回list2，反之亦然，因此这是一个边界情况；否则两者都存在时，当前node的next的next其实应该是返回比较小的那个值（为什么是返回？因为要与上面画横线的地方相对应）我们可以得到：

这样写清爽得多，在子递归中我们也表明了方向。

完整代码如下：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果其中一个链表为空，直接返回另一个链表
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 递归地选择较小的节点作为合并后的头节点
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

虽然递归也要使用空间，但至少空间消耗比原来低一些，代码则简单太多了。所以我们对于链表、树节点的处理，尽量要考虑递归。

---

第二题：22. 括号生成 - 力扣（LeetCode）

class Solution {
    List<String> res = new ArrayList<>();
    List<Character> path = new ArrayList<>();
 
    public List<String> generateParenthesis(int n) {
        int[] flag = new int[2];
        traversal(0, n, flag);
        return res;
    }
 
    private void traversal(int startindex, int n, int[] flag){
        if(startindex == n * 2){
            StringBuilder sb = new StringBuilder();
            for(char ch : path){
                sb.append(ch);
            }
            res.add(sb.toString());
            return;
        }
        if(flag[0] < n){
            // 讨论加入左括号的情况
            path.add('(');
            flag[0]++;
            traversal(startindex + 1, n, flag);
            flag[0]--;
            path.remove(path.size() - 1);
        }
        if(flag[0] > flag[1]){
            //只有在左边括号存在的数量大于右边的时候，
            //才可以考虑加入右括号，否则不匹配了
            path.add(')');
            flag[1]++;
            traversal(startindex + 1, n, flag);
            flag[1]--;
            path.remove(path.size() - 1);
        }
    }
}

---

第三题：23. 合并 K 个升序链表 - 力扣（LeetCode）

这道题不好处理，咱们直接考虑使用优先级队列来做，反正是升序，具体过程交给优先级队列来做，我们就负责把所有的值添加进去

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1, ListNode o2){
                return (o1.val) - (o2.val);
            }
        });
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }
 
        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
 
}

---

第四题：24. 两两交换链表中的节点 - 力扣（LeetCode）

class Solution {
    public ListNode swapPairs(ListNode head) {
        //特殊情况
        if(head == null || head.next == null){
            return head;
        }
        //dummy头节点
        ListNode dummyhead = new ListNode(-1, head);
        ListNode cur = dummyhead;
        //注意这里为什么是判断第二三个节点存在？
        while(cur.next != null && cur.next.next != null){
            //用变量名指代一下，不然看起来太复杂了
            ListNode A = cur.next, B = cur.next.next;
            cur.next = B;
            A.next = B.next;
            B.next = A;
            cur = cur.next.next;
        }
        return dummyhead.next;
    }
}

---

 第五题：25. K 个一组翻转链表 - 力扣（LeetCode）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            //剩余数量小于k的话，则不需要反转。
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(head, tail);
        //下一轮的开始的地方就是tail
        head.next = reverseKGroup(tail, k);
 
        return newHead;
    }
 
    // 左闭右开区间
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

---