1. 反转链表 ：

反转链表是常见简单题目，定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

第一次自己实现使用了栈来完成 。详见我的成功程序 ：

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

    public ListNode reverseList(ListNode head) {
        if(head == null) return null ; 
        Stack<ListNode> stackNode = new Stack<>() ;
        while(head != null){
            stackNode.push(head) ;
            head = head.next ;
        }
        //这里需要按照pop出的Node的结点值新建Node，否则会有Cycle ListNode 
        ListNode newReturn = new ListNode(stackNode.pop().val) ;
        ListNode tail = newReturn;
        while(!stackNode.isEmpty()){
            ListNode tp = new ListNode(stackNode.pop().val);
            tail.next = tp ;
            tail = tail.next ;
        }
        return newReturn ; 
    }

经过题解，如果使用双指针可以更快解决。讲解视频 ：https://ke.qq.com/webcourse/index.html#cid=3065907&term_id=103186001&taid=10593313500350515&type=1024&vid=5285890809407997971

    //双指针法 ：
    public ListNode reverseList(ListNode head) {
        ListNode pre = null ;
        ListNode curr = head ;
        while(curr != null){
            ListNode next = curr.next ;
            curr.next = pre ;
            pre = curr ;
            curr = next ;
        }
        return pre ;
    }

2. 设计和实现一个 LRU (最近最少使用) 缓存机制 ，一个数据结构：

该数据结构应该具有以下API操作 ：

定义一个LRUCache类 ：
1. LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存
2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
3. void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

这里通过key来返回value，很容易想到使用HashMap来实现这个数据结构，但是hashmap无法解决的是记录最近访问的功能， 所以就使用双链表来记录时间问题。 这里使用了dummy节点 head 和tail来方便操作（边界条件就能简单解决了）。 那么靠近head的结点的就是新的节点，而靠近tail的节点是历史结点。

这里双链表结构中，定义了2个值，是key、value ； 主要是在put溢出场景中，需要删除尾节点，同时在HashMap中也删除，所以这里双链表如果同时记录了key和value，那么就非常快的拿到了key，并按照这个key来remove掉HashMap中的元素。
下面是详细的代码实现 ：

class LRUCache {

    class DoubleLinkNode{
        private DoubleLinkNode next ;
        private DoubleLinkNode prev ;
        private int key ;
        private int val ;
        DoubleLinkNode(){}
        DoubleLinkNode(int _key, int _value){
            this.key =_key ;
            this.val =_value ;
        }
    }

    Map<Integer,DoubleLinkNode> map = new HashMap<>() ;
    //数据结构的容量
    private int capacity ;
    //数据结构目前的元素数量，在判断是否溢出时使用
    private int size;
    //伪头、尾结点
    DoubleLinkNode head ,tail ;

    public LRUCache(int capacity) {
        head = new DoubleLinkNode() ;
        tail = new DoubleLinkNode() ;
        head.next = tail ;
        tail.prev = head ;
        this.size = 0 ;
        this.capacity = capacity;
    }

    /**
     * 实现的主要的put方法：
     * @param key
     * @param value
     */
    public void put(int key, int value) {
       DoubleLinkNode node =  map.get(key) ;
       if(node ==null){
           //新建一个DoubleLink结点，HashMap中put新<key,value>
           DoubleLinkNode newNode = new DoubleLinkNode(key,value) ;
           map.put(key,newNode) ;
           addToHead(newNode);
           ++size;

           if(size > capacity){
            DoubleLinkNode tail = removeTail();
            map.remove(tail.key);
            --size ;
           }
       }
       else{
           node.val = value ;
           moveToHead(node);
       }
    }

    private DoubleLinkNode removeTail() {
        DoubleLinkNode oldTail = tail.prev ;
        oldTail.prev.next = tail ;
        tail.prev = oldTail.prev ;
        return oldTail ;
    }

    /**
     * 实现的主要的get方法
     * @param key
     * @return
     */
    public int get(int key) {
        DoubleLinkNode getD = map.get(key) ;
        if(getD == null){
            return  -1;
        }
        moveToHead(getD) ;
        return getD.val;
    }

    private void moveToHead(DoubleLinkNode getD) {
        removeNode(getD) ;
        addToHead(getD);
    }

    /**
     * 把结点增加到头结点上
     * @param getD
     */
    private void addToHead(DoubleLinkNode getD) {
        DoubleLinkNode oldFirst = head.next ;
        head.next = getD ;
        getD.next = oldFirst ;
        getD.prev = head;
        oldFirst.prev = getD ;
    }

    /**
     * 删除双链表中的一个结点
     * @param getD
     */
    private void removeNode(DoubleLinkNode getD) {
        DoubleLinkNode before = getD.prev ;
        DoubleLinkNode after = getD.next ;
        before.next = after;
        after.prev = before;
    }
}

3. 树的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径至少包含一个 节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
使用树中常见的递归方法，问自己的左右孩子要结果。 下面是我提交的java代码 ：

class Solution {
    int maxSum = Integer.MIN_VALUE ;

    public int maxPathSum(TreeNode root){
        maxSumDv(root) ;
        return maxSum ; 
    }

    public int maxSumDv(TreeNode root) {
        if(root == null) return 0 ;

        int leftSum = Integer.max(maxSumDv(root.left),0) ;
        int rightSum = Integer.max(maxSumDv(root.right),0) ;

        //本结点贡献的最大值 本结点贡献只能是单root 或者 root + root.left 或者 root + root.right
        int thisMaxSum = root.val + Integer.max(leftSum,rightSum);

        //更新最大值，最大值是跳出递归的全局变量
        maxSum = Integer.max(root.val + leftSum + rightSum,maxSum) ;

        return thisMaxSum ;
    }
}