Leetcode21-22【参加笔试】 下一次补回来

21. 合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }

        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null ) {
            cur.next = l2;
        }
        return dummy.next;
    }
}

22. 括号生成

能往里面加左括号的前提是左括号的数量小于右括号， 右括号能往里加的前提是小于等于规定的数量n

class Solution {
    int n;
    List<String> res;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        res = new ArrayList();
        dfs(0,  0, new StringBuilder());   
        return res;     
    }
    private void dfs(int lc, int rc, StringBuilder builder) {
        if (lc == n && rc == n) {
            res.add(builder.toString());
        } else {
            if (lc < n) {
                dfs(lc + 1, rc, new StringBuilder(builder).append('('));
            }
            if ( rc < lc) {
                dfs(lc, rc + 1, new StringBuilder(builder.append(')')));
            }
        }

    }

}

23. 合并K个升序链表

/**
 * 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 {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next != null)  {pq.offer(node.next);}
        }
        return dummy.next;
    }
}

24. 两两交换链表中的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {

        ListNode dummy = new ListNode(-1); 
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null) {
            ListNode p = cur.next;
            ListNode q = cur.next.next;
            cur.next = q;
            p.next = q.next;
            q.next = p;
            cur = p;

        }
        return dummy.next;
    }
}