LeetCode算法代码笔记（21-25）

给自己的目标：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一题

在做题的过程中记录下解题的思路或者重要的代码碎片以便后来翻阅。
项目源码：github上的Leetcode

21. Merge Two Sorted Lists

题目：给出两个有序的字节列表，将其按照大小合并。

与题目4的解题思路相同，同样也是从两个头部开始逐步比较大小。

/**
 * 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 head = new ListNode(-1);
        ListNode temp = head;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                head.next = l2;
                break;
            } else if (l2 == null) {
                head.next = l1;
                break;
            }
            if (l1.val <= l2.val) {
                head.next = l1;
                l1 = l1.next;
                head = head.next;
            } else {
                head.next = l2;
                l2 = l2.next;
                head = head.next;
            }
        }
        return temp.next;
    }
}

22. Generate Parentheses

题目：给出一个数值 n,求能生成所有合法结构的组合。

 For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

一道基础的深度优先算法，当左括号的个数小于右括号的个数时退出循环递归。当左括号和右括号为0时，加入结果集。

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> temp = new ArrayList<>();
        generateP("",n,n,temp);
        return temp;
    }
    
    public void generateP(String str, int left, int right, List<String> list) {
        if (left > right) {
            return;
        }
        if (left > 0) {
            generateP(str + "(", left - 1, right, list);
        }
        if (right > 0) {
            generateP(str + ")", left, right - 1, list);
        }
        if (left == 0 && right == 0) {
            list.add(str);
        }
    }
}

23. Merge k Sorted Lists

题目：合并多个有序的节点列表，要求按大小排列。
最初是两两从头合并导致 TLE。之后使用归并排序来进行优化。
归并操作：将两个顺序合并成一个顺序序列的方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<ListNode> list = new ArrayList<>();
        Collections.addAll(list, lists);
        return mergeKLists(list);
    }

   public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) return null;
        if (lists.size() == 1) return lists.get(0);

        int length = lists.size();
        int mid = (length - 1) / 2;
        ListNode l1 = mergeKLists(lists.subList(0, mid + 1));
        ListNode l2 = mergeKLists(lists.subList(mid + 1, length));
        return merge2Lists(l1, l2);
    }
    
    public  ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        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 = l1;
        } else if (l2 != null) {
            temp.next = l2;
        }
        return head.next;
    }
}

24. Swap Nodes in Pairs

题目： 给出一个字节列表，两个数为一组进行交换。节点里面的 val 是无法被改变的。

Given 1->2->3->4, you should return the list as 2->1->4->3. 

交换时要知道四个数，交换的i1和i2，i1前一个数i0,i2的后一个数i3.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode v = new ListNode(-1);
        v.next = head;
        ListNode res = v;
        while (v.next != null && v.next.next != null) {
            ListNode temp = v.next;
            ListNode l1 = temp.next;
            ListNode l2 = temp.next.next;
            l1.next = temp;
            temp.next = l2;
            v.next = l1;
            v = v.next.next;
        }
        return res.next;
    }
}

25. Reverse Nodes in k-Group

题目：给出一组节点列表和一个数字，按组来反转节点，组里面数字的个数为输入时给出的数字。

For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5 

我的解法是先将所有 ListNode 放入队列中，再按照K值来进行反转。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        List<ListNode> nodeList = new ArrayList<>();
        while (head != null) {
            nodeList.add(head);
            head = head.next;
        }
        int size = nodeList.size();
        int start = 0;
        while (size >= k) {
            swapNodes(nodeList, start, start + k - 1);
            size = size - k;
            start = start + k;
        }
        ListNode v = nodeList.get(0);
        ListNode temp = v;
        for (int i = 1; i < nodeList.size(); i++) {
            temp.next = nodeList.get(i);
            temp = temp.next;
        }
        temp.next = null;
        return v;
    }
    
    public void swapNodes(List<ListNode> list, int start, int end) {
        if (end >= list.size()) {
            return;
        }
        while (start < end) {
            ListNode temp = list.get(start);
            list.set(start, list.get(end));
            list.set(end, temp);
            start++;
            end--;
        }
    }
}