找中间节点

High Level Idea:

1. Initialize 2 potinters i and j pointing to the head
2. While the next move of the faster pointer j is valid (inside bound), move j two steps and i one step forward
3. Return the node at i

   public ListNode linkedlistMiddleNode(ListNode head){
    ListNode i = head, j = head;
    while(j != null && i != null){
        i = i.next;
        j = j.next;
    }
    return i;
   }

找倒数第k个节点

High Level Idea:

1. Initialize two pointers i and j pointing to the head
2. Move j k steps forward
3. Move both i and j one step forward at a time until j is out of bound

public ListNode linkedlistLastKehNode(ListNode head, int k){
    ListNode i = head, j = head;
    for(int c = 0; c < k; c++){
        j = j.next;
    }
    while(j != null){
        i = i.next;
        j = j.next;
    }
    return i;
}

Recursion 递归翻转单链表

彻底翻转

Bottom up recursion 3 steps:

1. Ask for subproblem result
2. Do something in current level of recursion
3. Return result

Recursion 最重要的一点： 相信自己的recurisive function是正确的

High Level Idea:

1. Ask for next recursion level result
2. Reverse current node
3. Return reversed head

使用宏观思想思考递归，切勿跳进递归，base case是替罪羊

//Reverse Linked List
public ListNode reverse(ListNode head){
    if(head == null || head.next = null){    //base case
        return head;
    }
    ListNode reverse_head = reverse(head.next);    //宏观思维
    head.next.next = head;
    head.next = null;
    return reverse_head;    //new head
}

反转链表前N个节点

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {     //base case 替罪羊
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

具体的区别：

1. base case 变为n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
2. 刚才我们直接把head.next设置为 null，因为整个链表反转后原来的head变成了整个链表的最后一个节点。但现在head节点在递归反转之后不一定是最后一个节点了，所以要记录后驱successor（第 n + 1 个节点），反转之后将head连接上。

补充资料 https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/bu-bu-chai-jie-ru-he-di-gui-di-fan-zhuan-lian-biao/