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

在做題的過程中記錄下解題的思路或者重要的代碼碎片以便后來翻閱。
項目源碼：github上的Leetcode

21. Merge Two Sorted Lists

題目：給出兩個有序的字節(jié)列表，將其按照大小合并。

與題目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

題目：給出一個數(shù)值 n,求能生成所有合法結(jié)構(gòu)的組合。

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

一道基礎(chǔ)的深度優(yōu)先算法，當左括號的個數(shù)小于右括號的個數(shù)時退出循環(huán)遞歸。當左括號和右括號為0時，加入結(jié)果集。

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

題目：合并多個有序的節(jié)點列表，要求按大小排列。
最初是兩兩從頭合并導致 TLE。之后使用歸并排序來進行優(yōu)化。
歸并操作：將兩個順序合并成一個順序序列的方法

/**
 * 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

題目： 給出一個字節(jié)列表，兩個數(shù)為一組進行交換。節(jié)點里面的 val 是無法被改變的。

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

交換時要知道四個數(shù)，交換的i1和i2，i1前一個數(shù)i0,i2的后一個數(shù)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

題目：給出一組節(jié)點列表和一個數(shù)字，按組來反轉(zhuǎn)節(jié)點，組里面數(shù)字的個數(shù)為輸入時給出的數(shù)字。

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值來進行反轉(zhuǎn)。

/**
 * 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--;
        }
    }
}