Singly Linked List常用解题技巧

1. Iterate the LinkedList to get total length.

int len=0;
for(ListNode head = root; head != null; head = head.next) len++;

2. Find the middle node of the LinkedList.
   use fast and slow pointers

private ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

长度是奇数时middle是中间的数：1->2->3->4->5
长度是偶数时middle是后半部分第一个：1->2->3->4

3. Reverse LinkedList

private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}