import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * http://blog.csdn.net/luckyxiaoqiang/article/details/7393134 輕松搞定面試中的鏈表題目
 * http://www.rzrgm.cn/jax/archive/2009/12/11/1621504.html 算法大全（1）單鏈表
 * 
 * 目錄：
 * 1. 求單鏈表中結點的個數: getListLength 
 * 2. 將單鏈表反轉: reverseList（遍歷），reverseListRec（遞歸）
 * 3. 查找單鏈表中的倒數第K個結點（k > 0）: reGetKthNode 
 * 4. 查找單鏈表的中間結點: getMiddleNode 
 * 5. 從尾到頭打印單鏈表: reversePrintListStack，reversePrintListRec（遞歸）
 * 6. 已知兩個單鏈表: pHead1 和pHead2 各自有序，把它們合并成一個鏈表依然有序: mergeSortedList, mergeSortedListRec 
 * 7. 判斷一個單鏈表中是否有環: hasCycle 
 * 8. 判斷兩個單鏈表是否相交: isIntersect 
 * 9. 求兩個單鏈表相交的第一個節點: getFirstCommonNode
 * 10. 已知一個單鏈表中存在環，求進入環中的第一個節點: getFirstNodeInCycle, getFirstNodeInCycleHashMap
 * 11. 給出一單鏈表頭指針pHead和一節點指針pToBeDeleted，O(1)時間復雜度刪除節點pToBeDeleted: delete
 * 
 */
public class ListSummary {

    public static void main(String[] args) {
        ListNode n1 = ListUtils.makeList(1, 2, 3, 4, 5);

        ListUtils.printList(n1);

        ListNode x = reGetKthNode(n1, 2);
        System.out.println(x.val);

    }

    // 求單鏈表中結點的個數
    // 注意檢查鏈表是否為空。時間復雜度為O（n）
    public static int getListLength(ListNode head) {
        // 注意頭結點為空情況
        if (head == null) {
            return 0;
        }

        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }

    // 翻轉鏈表（遍歷） pre,cur,post的運用
    // 注意鏈表為空和只有一個結點的情況。時間復雜度為O（n）
    public static ListNode reverse(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
            ListNode post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }
        head.next = null;
        return pre;
    }

    // 翻轉遞歸（遞歸）
    // 遞歸的精髓在于你就默認reverseListRec已經成功幫你解決了子問題了！但別去想如何解決的
    public static ListNode reverseListRec(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode reHead = reverseListRec(head.next);
        head.next.next = head; // 把head接在reHead串的最后一個后面
        head.next = null; // 防止循環鏈表
        return reHead;
    }

    /**
     * 查找單鏈表中的倒數第K個結點（k > 0） 主要思路就是使用兩個指針，先讓前面的指針走到正向第k個結點
     * 這樣前后兩個指針的距離差是k-1，之后前后兩個指針一起向前走，前面的指針走到最后一個結點時，后面指針所指結點就是倒數第k個結點
     * 注意k>len的情況如何處理
     */
    public static ListNode reGetKthNode(ListNode head, int k) {
        if (k <= 0)
            return null;

        ListNode s = head;
        ListNode f = head;
        for (int i = 0; i < k - 1 && f != null; i++)
            f = f.next;

        if (f == null)// k is larger than len
            return null;

        while (f.next != null) {
            s = s.next;
            f = f.next;
        }
        return s;
    }

    // 查找單鏈表的中間結點
    /**
     * 此題可應用于上一題類似的思想。也是設置兩個指針，只不過這里是，兩個指針同時向前走，前面的指針每次走兩步，后面的指針每次走一步，
     * 前面的指針走到最后一個結點時，后面的指針所指結點就是中間結點，即第（n/2+1）個結點。注意鏈表為空，鏈表結點個數為1和2的情況。時間復雜度O（n
     */
    public static ListNode getMiddleNode(ListNode head) {

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

        return slow;
    }

    /**
     * 從尾到頭打印單鏈表
     * 對于這種顛倒順序的問題，我們應該就會想到棧，后進先出。所以，這一題要么自己使用棧，要么讓系統使用棧，也就是遞歸。注意鏈表為空的情況
     * 。時間復雜度為O（n）
     */
    public static void reversePrintListStack(ListNode head) {
        Stack<ListNode> s = new Stack<ListNode>();
        ListNode cur = head;
        while (cur != null) {
            s.push(cur);
            cur = cur.next;
        }

        while (!s.empty()) {
            cur = s.pop();
            System.out.print(cur.val + " ");
        }
        System.out.println();
    }

    /**
     * 從尾到頭打印鏈表，使用遞歸（優雅！）
     */
    public static void reversePrintListRec(ListNode head) {
        if (head == null) {
            return;
        } else {
            reversePrintListRec(head.next);
            System.out.print(head.val + " ");
        }
    }

    /**
     * 已知兩個單鏈表pHead1 和pHead2 各自有序，把它們合并成一個鏈表依然有序
     * 這個類似歸并排序。尤其注意兩個鏈表都為空，和其中一個為空時的情況。只需要O（1）的空間。時間復雜度為O（max(len1, len2)）
     */
    public static ListNode mergeSortedList(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        ListNode p1 = l1;
        ListNode p2 = l2;

        ListNode head = new ListNode(-1);
        ListNode p = head;

        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null)
            p.next = p1;
        if (p2 != null)
            p.next = p2;

        return head.next;

    }

    /**
     * 遞歸合并兩鏈表（優雅！）
     */
    public static ListNode mergeSortedListRec(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        ListNode mergeHead = null;
        if (head1.val < head2.val) {
            mergeHead = head1;
            mergeHead.next = mergeSortedListRec(head1.next, head2);
        } else {
            mergeHead = head2;
            mergeHead.next = mergeSortedListRec(head1, head2.next);
        }
        return mergeHead;
    }

    /**
     * 判斷一個單鏈表中是否有環
     * 這里也是用到兩個指針。如果一個鏈表中有環，也就是說用一個指針去遍歷，是永遠走不到頭的。因此，我們可以用兩個指針去遍歷，一個指針一次走兩步
     * ，一個指針一次走一步，如果有環，兩個指針肯定會在環中相遇。時間復雜度為O（n）
     */
    public static boolean hasCycle(ListNode head) {
        ListNode fast = head; // 快指針每次前進兩步
        ListNode slow = head; // 慢指針每次前進一步

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { // 相遇，存在環
                return true;
            }
        }
        return false;
    }

    // 判斷兩個單鏈表是否相交
    /**
     * 如果兩個鏈表相交于某一節點，那么在這個相交節點之后的所有節點都是兩個鏈表所共有的。 也就是說，如果兩個鏈表相交，那么最后一個節點肯定是共有的。
     * 先遍歷第一個鏈表，記住最后一個節點，然后遍歷第二個鏈表， 到最后一個節點時和第一個鏈表的最后一個節點做比較，如果相同，則相交，
     * 否則不相交。時間復雜度為O(len1+len2)，因為只需要一個額外指針保存最后一個節點地址， 空間復雜度為O(1)
     */
    public static boolean isIntersect(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return false;
        }

        ListNode tail1 = head1;
        // 找到鏈表1的最后一個節點
        while (tail1.next != null) {
            tail1 = tail1.next;
        }

        ListNode tail2 = head2;
        // 找到鏈表2的最后一個節點
        while (tail2.next != null) {
            tail2 = tail2.next;
        }

        return tail1 == tail2;
    }

    /**
     * 求兩個單鏈表相交的第一個節點 對第一個鏈表遍歷，計算長度len1，同時保存最后一個節點的地址。
     * 對第二個鏈表遍歷，計算長度len2，同時檢查最后一個節點是否和第一個鏈表的最后一個節點相同，若不相同，不相交，結束。
     * 兩個鏈表均從頭節點開始，假設len1大于len2
     * ，那么將第一個鏈表先遍歷len1-len2個節點，此時兩個鏈表當前節點到第一個相交節點的距離就相等了，然后一起向后遍歷，直到兩個節點的地址相同。
     * 時間復雜度，O(len1+len2)
     * 
     * ---- len2 |__________ | --------- len1 |---|<- len1-len2
     */
    public static ListNode getFirstCommonNode(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        int len1 = 1;
        ListNode tail1 = head1;
        while (tail1.next != null) {
            tail1 = tail1.next;
            len1++;
        }

        int len2 = 1;
        ListNode tail2 = head2;
        while (tail2.next != null) {
            tail2 = tail2.next;
            len2++;
        }

        // 不相交直接返回NULL
        if (tail1 != tail2) {
            return null;
        }

        ListNode n1 = head1;
        ListNode n2 = head2;

        // 略過較長鏈表多余的部分
        if (len1 > len2) {
            int k = len1 - len2;
            while (k != 0) {
                n1 = n1.next;
                k--;
            }
        } else {
            int k = len2 - len1;
            while (k != 0) {
                n2 = n2.next;
                k--;
            }
        }

        // 一起向后遍歷，直到找到交點
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }

        return n1;
    }

    /**
     * 求進入環中的第一個節點 用快慢指針做（本題用了Crack the Coding Interview的解法，因為更簡潔易懂！）
     */
    public static ListNode getFirstNodeInCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean meet = false;

        // 1） 找到快慢指針相遇點
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { // Collision
                meet = true;
                break;
            }
        }

        // 錯誤檢查，這是沒有環的情況
        if (!meet) {
            return null;
        }

        // 2）現在，相遇點離環的開始處的距離等于鏈表頭到環開始處的距離，
        // 這樣，我們把慢指針放在鏈表頭，快指針保持在相遇點，然后
        // 同速度前進，再次相遇點就是環的開始處！
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // 再次相遇點就是環的開始處
        return fast;
    }

    /**
     * 求進入環中的第一個節點 用HashMap做 一個無環的鏈表，它每個結點的地址都是不一樣的。
     * 但如果有環，指針沿著鏈表移動，那這個指針最終會指向一個已經出現過的地址 以地址為哈希表的鍵值，每出現一個地址，就將該鍵值對應的實值置為true。
     * 那么當某個鍵值對應的實值已經為true時，說明這個地址之前已經出現過了， 直接返回它就OK了
     */
    public static ListNode getFirstNodeInCycleHashMap(ListNode head) {
        HashMap<ListNode, Boolean> map = new HashMap<ListNode, Boolean>();
        while (head != null) {
            if (map.get(head) == true) {
                return head; // 這個地址之前已經出現過了，就是環的開始處
            } else {
                map.put(head, true);
                head = head.next;
            }
        }
        return head;
    }

    /**
     * 給出一單鏈表頭指針head和一節點指針toBeDeleted，O(1)時間復雜度刪除節點tBeDeleted
     * 對于刪除節點，我們普通的思路就是讓該節點的前一個節點指向該節點的下一個節點
     * ，這種情況需要遍歷找到該節點的前一個節點，時間復雜度為O(n)。對于鏈表，
     * 鏈表中的每個節點結構都是一樣的，所以我們可以把該節點的下一個節點的數據復制到該節點
     * ，然后刪除下一個節點即可。要注意最后一個節點的情況，這個時候只能用常見的方法來操作，先找到前一個節點，但總體的平均時間復雜度還是O(1)
     */
    public void delete(ListNode head, ListNode toDelete) {
        if (toDelete == null) {
            return;
        }
        if (toDelete.next != null) { // 要刪除的是一個中間節點
            toDelete.val = toDelete.next.val; // 將下一個節點的數據復制到本節點!
            toDelete.next = toDelete.next.next;
        } else { // 要刪除的是最后一個節點！
            if (head == toDelete) { // 鏈表中只有一個節點的情況
                head = null;
            } else {
                ListNode node = head;
                while (node.next != toDelete) { // 找到倒數第二個節點
                    node = node.next;
                }
                node.next = null;
            }
        }
    }
    

}