每日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>(){@Overridepublic 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);//下一轮的开始的地方就是tailhead.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;}
}