打广告：java技术交流群：130031711，欢迎各位萌新大佬踊跃加入。

奇偶链表

题目：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

思路：暂时来说这个题的思路就是快慢指针。然后节点的取出和插入。快指针每次指向的肯定是奇数节点，所以放在前面。我感觉我这个思路是没问题的，时间空间复杂度都可以满足，我去试试看吧。
一次ac，还是蛮简单的题目。我直接贴代码不多BB了：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null || head.next==null || head.next.next==null) return head;
        //奇数
        ListNode slow = head;
        //偶数
        ListNode fast = head.next;
        //最后slow和fast都会指向最后，所以要记录偶数的开始位置
        ListNode o = fast;
        while(fast != null && slow != null && fast.next!=null && slow.next!=null){
            //奇数节点放到slow后面
            slow.next = fast.next;  
            slow = slow.next;  
            //偶数节点放到fast后面       
            fast.next = slow.next;
            fast = fast.next;
        }
        slow.next = o; 
        return head;
    }
}

这个题我觉得是没什么难点，可能稍微有点问题的就是刚接触链表可能这个插入和取出会不太好一下子想出来。我也是做了好多类似的题才会一下子有思路的，反正就这样吧，时间空间复杂度都合格，下一题了。

验证二叉树的前序序列化

题目：序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:
输入: "1,#"
输出: false
示例 3:
输入: "9,#,#,1"
输出: false

思路：说个题外话，刚刚有个一起刷题的小姐姐邀请我4.25力扣编程大赛的组队。。其实统共也报名了几次leetcode的周赛，感觉自己现在的水平就是简单的百分之九十没问题，中等的要看运气做出一两道。最后困难的别说会不会了，大多数情况看的时间都莫得。。。然后这个一直攻略困难题目的小姐姐邀请我，有点小开心哈~！咱们继续说这个题吧。这个题我觉得有一点：如果按照空位补0的情况，起码这个数要是奇数的。因为根节点是一个，剩下都是成对出现，所以元素的个数一定是奇数个数。其次就是每一层个数，如果有一个#，则下一层在满数的情况下少2个，依次判断。我去实现看看。
思路没问题，细节处理可能不太好，但是题目还是很清晰明了的，我直接贴代码：

class Solution {
    int len;
    public boolean isValidSerialization(String preorder) {       
        String[] str = preorder.split(",");
        len = str.length;
        if(str.length%2!=1) return false;
        return dfs(str,1,0);
        
    }
    public boolean dfs(String[] str,int n,int start){
        if(len<(start+n))return false;//剩下元素数不够了直接false
        int num = n;
        for(int i = 0;i<n;i++){
            if(str[start+i].equals("#")) num--;
        }
        //最后一层正好都是#则true
        if(num==0 && len == (start+n)) return true;
        //不应该有下一层元素了，但是前序序列化中还有元素
        if(num==0) return false;
        return dfs(str,num*2,start+n);
    }
}

首先奇偶数的那个上面说了思路，其次最后一层肯定都是#才对。下一层是上一层数目的两倍。反正我觉得条件啥的挺明确的。这道题就这样吧。
我这个代码是4ms，超过百分之八十七的人。我觉得大体思路没错。改进的话字符串equals这块耽误性能了可能，但是这里用char也不合适，毕竟数字有可能会好几位数。。算了，我直接看题解吧。
性能排行第一的代码：

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return false;
        }
        int nodesNum = 0;
        char[] chars = preorder.toCharArray();
        int length = preorder.length();
        int i = 0;
        for (; i < length;) {
            if (chars[i] == ',') {
                ++i;
            } else if (chars[i] == '#') {
                if (nodesNum == 0) {
                    break;
                }
                ++i;
                --nodesNum;
            } else {
                ++nodesNum;
                ++i;
                while (i < length && chars[i] != '#' && chars[i] != ',') {
                    ++i;
                }
            }
        }
        return nodesNum == 0 && i == length - 1;
    }
}

怎么说呢，其实我觉得我已经找到约束条件了，只不过和人家的一比，还是太年轻啊。我是看了人家的代码反推回去才发现，如果都是空白补#，#的数量应该比实际上的已有值的节点数多一个。另外因为是前序排列，所以不能只看最后总数结果，必须保证不会出现上一层都是#下一层还有元素的情况，所以一旦#数多了则直接return。
图中性能第一的代码是用正常节点数减去空节点数。如果出现不够减的情况说明false。最后如果正常节点数没了并且遍历到序列的最后说明是对的，返回true不然就是false。
这道题只能说实现简单，但是像人家这么思路清楚的实现我没做到。下次记得了，下一趟吧。

重新安排行程

题目：给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:
如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
示例 1:
输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:
输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

思路：感觉这个题可以用邻接链表实现？至于说的自然排序，我也没太看明白排序的规则。反正先试试看吧。反正感觉这个题不难。jfk是0度的作为开始，剩下的因为确定是存在合理形成的，所以正常遍历就好了吧？我去写代码试试。
好好一个题目让我做的稀碎。中间改了n多次想法。本来想的入度，结果出来发现有的是死路。所以这个想法就破灭了，但是我觉得大方向还是不会错的。所以换了回溯。主要是真的我觉得这种题麻烦的是数据格式，然后处理来处理去，最后用回溯+递归实现了，我直接贴下代码：

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Stack<String> stack = new Stack<String>();
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        for (List<String> list : tickets) {
            String start = list.get(0);
            String end = list.get(1);
            if (!map.containsKey(start)) {
                map.put(start, new ArrayList<>());
            }
            map.get(start).add(end);
        }
        //排序
        for (String s : map.keySet()) {
            Collections.sort(map.get(s));
        }
        List<String> path = new ArrayList<>();
        DFS(map, "JFK", path, tickets.size() + 1);
        return path;
    }
    public boolean DFS(Map<String, List<String>> map, String s, List<String> path, int len){
        //整体是个大回溯、add——操作——remove，会回溯就说明此路不通，直接换成最近选择的口换个选择继续试。
        path.add(s);
        //走到最后了
        if (path.size() == len) {
            return true;
        }
        
        List<String> next = map.get(s);
        if (next != null) {
            for (int i = 0; i < next.size(); ++i) {
                String nextS = next.get(i);
                //这个票往下走不下去了。
                if (nextS == null) {
                    continue;
                }
                //这个票正在走，所以下一个节点暂时为0.防止成环死递归
                next.set(i, null);
                if (DFS(map, nextS, path, len)) {
                    return true;
                } 
                next.set(i, nextS);
            }
        }
        path.remove(path.size() - 1);
        return false;
    }
}

然后因为代码逻辑比较复杂，我注释写的很墨迹，说真的，一般我注释都是给自己看的，怕坑着坑着不知道当时为啥这么写代码了。哈哈反正得品，细品。
做出来了发现逻辑其实不难，但是调试的时候真的心态炸。也可能是思路不清楚吧。
反正最终是实现了，大体逻辑：

• 首先变成map数组。然后互通关系要找好。稍微好点的是开始城市到结束城市不能互换。所以单向关系就好。
• 然后第二步是排序（因为说了按自然排序，我也不知道自然是谁，而且我觉得list也没法自己排序，所以我用了sort，这个最自然了。）
• 第三步是找到一个途径。找的过程是回溯+递归。中间有个注意点是递归过程中已经用了的车次要暂时设置为null。不然可能就是过去回来过去回来陷入死循环。然后如果走到某条路不能走了说明不对，退到最近的岔路口，换条路。回溯也是这里用的。
  因为之前排序了，所以第一个到达终点（全都跑一遍就是到达终点了。而且是起始的，所以总长度+1。）就是最小自然排序的那个结果。
  总体来说思路就这样，具体实现中的坑不自己试一遍容易记不住，千奇百怪的。
  看了下性能排行第一的代码，思路是差不多的思路，只不过我是用list实现每个出发地对应的目的地，而且还要单独排序，但是人家用了一种自带排序的队列，处理起来比较优雅吧。我直接贴代码：

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> res = new ArrayList<>();
        if (tickets.size() == 0) {
            return res;
        }
        HashMap<String, PriorityQueue<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            if (map.get(from) == null) {
                map.put(from, new PriorityQueue<>());
            }
            map.get(from).offer(to);
        }

        findItineraryHelper(map, res, "JFK");
        return res;
    }

    public void findItineraryHelper(HashMap<String, PriorityQueue<String>> map, List<String> res, String from) {
        PriorityQueue<String> to = map.get(from);
        if (to != null) {
            while (!to.isEmpty()) {
                findItineraryHelper(map, res, to.poll());
            }
        }
        res.add(0, from);
    }
}

这个代码我觉得利用数据结构到极致了，其实这个PriorityQueue我是知道的，之前做题的时候也用过。不过可惜的是在这里没想到用它。
而且还有一点，递归中是逆序插入的，就是每次都插入到第一个元素中。而且是每个元素无路可走了才会被插入到结果集。保证了最小的元素最后被插入到结果集，也就是到了最前面的位置。附上一个leetcode大佬的图：

逆序插入