package cn.infobuy.gouqi.demo;

import cn.infobuy.gouqi.util.ListNode;
import cn.infobuy.gouqi.util.TreeNode;

/**
 * 关于链表
 * @author JohnLiu
 *
 */
public class ListSolution {
    /**
     * 链表反转
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode current = head;
        int count = 0;
        ListNode partHead=null;
        ListNode partEnd=null;
        while(current!=null) {
            // 表示当前的节点是第counter个节点
            count++;
            if(count==m-1) {
                partHead=current;
            }
            if(count==n+1) {
                partEnd=current;
            }
            current = current.next;
        }
        if(partHead==null) {
            return reverseList(head, partEnd);
        }else {
            ListNode newPartHead = reverseList(partHead.next, partEnd);
            partHead.next=newPartHead;
            return head;
        }
    }
    /**
     * 旋转链表
     * 给定一个链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k <= 0) {
            return head;
        }
        ListNode current = head;
        int n = 1;
        //O(n)
        while (current.next != null) {
            n++;
            current = current.next;
        }

        current.next = head;

        int count = n - k % n;
        ListNode result = null;
        for (int i = 0; i < count; i++) {
            current = current.next;
        }
        result = current.next;
        current.next = null;
        return result;
    }
    /**
     * k个一组翻转链表
     * 递归版本
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup1(ListNode head, int k) {
        ListNode current_node = head;
        int count = 0;
        while (current_node != null && count != k) {
            current_node = current_node.next;
            count++;
        }
        if (count == k) {
            current_node = reverseKGroup(current_node, k);/// 递归的解决子问题
            while (count-- > 0) {
                ListNode temp = head.next;
                head.next = current_node;
                current_node = head;
                head = temp;
            }///最终，该段的所有节点将会截空，head应指向current_node
            head = current_node;
        }
        return head;        
   }
    /**
     * k个一组翻转链表
     * 迭代版本
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode finalhead = new ListNode(0);
        finalhead.next=head;
        ListNode partHead = null;
        ListNode partNextHead = head;
        ListNode parent = finalhead;
        while((partHead=partNextHead)!=null){
            // 迭代寻找 partNextHead
            int tmpK = k-1;
            while((partNextHead=partNextHead.next)!=null&&tmpK>0){
                tmpK--;
            }
            if(tmpK>0){
                break;
            }
            reverseList(parent,partHead,partNextHead);
            parent=partHead;
        }
        return finalhead.next;
    }
    /**
     * 通过三个指针实现整个链表[head,endTarget.pre]的翻转
     * head：记录链表的头部
     * surplexHead: 记录链表剩余的头部
     * next：当前操作的节点
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head,ListNode end){
        ListNode currentNode = null;
        ListNode surplexHead = head;
        // 一个head指针专门记录处理完成后的head节点
        head=end;
        while(surplexHead!=end){
            currentNode = surplexHead;
            surplexHead=currentNode.next;
            currentNode.next=head;
            head=currentNode;
        }
        return head;
    }
    public void reverseList(ListNode parent,ListNode head,ListNode end){
        // 当前操作的指针
        ListNode currentNode = null;
        // 未操作的头指针
        ListNode surplexHead = head;
        // 已操作好的头指针
        head=end;
        while(surplexHead!=end){
            currentNode = surplexHead;
            surplexHead=surplexHead.next;
            currentNode.next=head;
            head=currentNode;
        }
        parent.next=head;
    }
    /**
     * 合并两个有序链表为一个有序链表
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null&&l2==null){
            return null;
        }
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if(l1.val>l2.val){
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
    /**
     * 合并K个排序链表
     * 合并2个会的，那合并k个呢？
     * 
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists==null||lists.length==0){
            return null;
        }
        return mergeLists(lists,0,lists.length-1);
    }
    /**
     * 利用归并排序的思想
     * k个列表，每次拆成2堆，然后每堆生成一个排序后的链表，再将两个排序后的链表升为一个链表并返回
     * 时间复杂度为 O(lg(K)kn)
     * @param lists
     * @param left
     * @param right
     * @return
     */
    private ListNode mergeLists(ListNode[] lists, int left, int right) {
        int mid = (left+right)/2;
        if (left<right){
            ListNode l1 = mergeLists(lists, left, mid);
            ListNode l2 = mergeLists(lists, mid + 1, right);
            return mergeTwoLists(l1,l2);
        }
        return lists[left]; //如果left==right则直接返回左面的链表
    }
    /**
     * 删除链表的倒数第N个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode reachEnd=head;
        ListNode reachNth=head;
        int depth=n;
        // 确保 reachEnd 比 reachNth 快 n步
        while(depth>=1){
            reachEnd=reachEnd.next;
            depth--;
        }
        ListNode markPreNode = null;
        while(reachEnd!=null){
            reachEnd=reachEnd.next;
            markPreNode=reachNth;
            reachNth=reachNth.next;
        }
        if(head==reachNth){
            // 如果head被删除了
            return head.next;
        }else{
            markPreNode.next=reachNth.next;
            return head;
        }
    }
    /**
     * 两两交换链表中的节点
     * 给定 1->2->3->4, 你应该返回 2->1->4->3.
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode a = new ListNode(0);
        a.next=head;
        head=a;
        while(head.next!=null&&head.next.next!=null){
            ListNode nextNode=head.next.next;
            ListNode firstNode = head.next;
            // swapPairs
            firstNode.next=nextNode.next;
            head.next=nextNode;
            nextNode.next=firstNode;
            // 迭代
            head=firstNode;
        }
        return a.next;
    }
    /**
     * 删除排序链表中的重复元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode l1 = head;
        //验证 head.next 是否要加入
        while(head!=null&&head.next!=null){
            if(head.next.val==head.val){
                head.next=head.next.next;
            }else{
                head = head.next;
            }
        }
        return l1;
    }
    /**
     * 删除排序链表中的重复元素 II
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        // 标记头节点
        ListNode parent = new ListNode(-1);
        ListNode certainTail = parent;
        // 第一个节点暂定为head
        certainTail.next=head;
        // 指定目前暂定的节点，考虑是否要加入certainTail链表中
        ListNode tmpTail = head;
        while(tmpTail!=null&&tmpTail.next!=null) {
            if(tmpTail.val!=tmpTail.next.val) {
                certainTail.next=tmpTail;
                certainTail=tmpTail;
                tmpTail=tmpTail.next;
            }else {
                while(tmpTail.next!=null&&tmpTail.val==tmpTail.next.val) {
                    tmpTail.next=tmpTail.next.next;
                }
                tmpTail=tmpTail.next;
                certainTail.next=tmpTail;
            }
        }
        return parent.next;
    }
    /**
     * 分隔链表
     * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
     * 你应当保留两个分区中每个节点的初始相对位置。
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        if(head==null) {
            return null;
        }
        ListNode top = head;
        ListNode current = null;
        // 验证head.next是否满足条件
        while(head.next!=null) {
            if(head.next.val<x) {
                current=head.next;
                head.next=head.next.next;
                current.next=top;
                top=current;
            }else {
                head = head.next;
            }
        }
        return top;
    }
    public ListNode partition2(ListNode head, int x) {
        ListNode top = new ListNode(0);
        top.next=head;
        head=top;
        ListNode current = null;
        ListNode newHead = null;
        ListNode newTail = null;
        // 验证head.next是否满足条件
        while(head.next!=null) {
            if(head.next.val<x) {
                current=head.next;
                head.next=head.next.next;
                if(newHead==null) {
                    newHead = current;
                    newTail = current;
                }else {
                    newTail.next=current;
                    newTail = current;
                }
            }else {
                head = head.next;
            }
        }
        if(newHead!=null) {
            newTail.next=top.next;
        }else {
            newHead = top.next;
        }
        return newHead;
    }
    /**
     * 将有序链表转为二叉树BST
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST(head,null);
    }
    public TreeNode sortedListToBST(ListNode head,ListNode end) {
        if(head==end) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=end&&fast.next!=end) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode c = new TreeNode(slow.val);
        c.left=sortedListToBST(head,slow);
        c.right=sortedListToBST(slow.next,end);
        return c;
    }
}