嘎嘎牛的经典算法Java练习3

快慢指针问题，链表中比较多见可以多看看
快慢指针：想让快指针走需要的步数，然后快慢一起走，当快指针到头时，慢指针所在位置就是所需位置

//https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?


public class 链表中倒数第k个结点 {
    public ListNode FindKthToTail(ListNode head,int k) {
        //合法性判断
        if (head == null || k <= 0){
            return null;
        }
        //定义一个临时链表进行对比
        ListNode cur = head;
        //先让临时链表把k步走了
        while (k > 0 && cur != null){
            cur = cur.next;
            k--;
        }
        //如果是因为k超出范围跳出来的就返回null
        if (k != 0){
            return null;
        }
        //此时是因为临时链表先走了k步，此时让他们共同进步，当临时链表走到头时此时链表所在位置就是倒数第k个结点
        while (cur != null){
            cur = cur.next;
            head = head.next;
        }
        return head;
    }
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}

注意看交换过程的注释哦～这是关键

//https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?


public class 反转链表 {
    public ListNode ReverseList_1(ListNode head) {
        //合法性判断注意head.next；否则这个方法会越界
        if (head == null || head.next == null){
            return head;
        }
        //定义三个结点进行转向操作
        ListNode node1 = head;
        ListNode node2 = node1.next;
        ListNode node3 = node2.next;
        //在node3没到头时，进行转换操作
        while (node3 != null){
            //把node2的链子串在node1上;然后三个一起向后移动一步
            node2.next = node1;
            node1 = node2;
            node2 = node3;
            node3 = node3.next;
        }
        //此时node3到头了，但是node2的链子还没转（也就是最后一个），再操作一下
        node2.next = node1;
        //全部转向成功了，把头节点重新定义一下
        head.next = null;//这部可以省略，jvm会处理，后续会更新jvm部分
        head = node2;
        return head;//可以直接node2
    }

    public ListNode ReverseList_2(ListNode head) {
        //合法性判断注意head.next；否则这个方法会越界
        if (head == null || head.next == null){
            return head;
        }
        ListNode newHead = null;
        while (head != null){
            //定义一个临时结点
            ListNode cur = head;
            //把头节点后移，方便下一次定义的临时结点是下一个元素
            head = head.next;
            //把定义的临时结点，（头节点变化前所在位置）链接到新头后面
            cur.next = newHead;
            //新头节点后移
            newHead = cur;
        }
        //循环完时新链表创建成功头在newHead那里
        return newHead;
    }

    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }

}

1、注意边界问题，和当前cur处理到哪里，保证连接的位置是正确的

//https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?


public class 链表合并 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        //定义边界重新构建链表
        ListNode head = null;
        ListNode tail = null;
        //循环两个链表进行判断
        while (list1 != null && list2 != null){
            //定义一个临时节点用来操作连接
            ListNode cur = null;
            //哪个值小就让哪个把临时节点放成它
            if (list1.val < list2.val){
                cur = list1;
                list1 = list1.next;
            }else {
                cur = list2;
                list2 = list2.next;
            }
            //此时临时节点就是小的值进行连接就好（连接到重新构建的链表上即head-tail）；
            //如果头空说明cur是第一个节点，直接放成头就好了，如果头不是空，连接在后面
            if (head == null){
                head = cur;
                tail = cur;
            }else {
                tail.next = cur;
                tail = tail.next;
            }
        }
        //while走完时，此时必定是有一个链表已经走到头了，把另一个链表插进去就好了
        tail.next = list1 == null ? list2 : list1;
        return head;
    }
    
    //题目给定链表类
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}

镜像树关系：

package demo3;
//https://www.nowcoder.com/questionTerminal/a9d0ecbacef9410ca97463e4a5c83be7


public class 二叉树的镜像 {
    public TreeNode Mirror (TreeNode pRoot) {
        //合法性判断
        if (pRoot == null)
            return null;
        //将根节点左右子树互换
        TreeNode cur = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = cur;
        //递归的处理其左右子树
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }

    //题目给定二叉树
    public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }
}

注意边界值的处理，pre是重复区间的前驱，last是最后一个重复节点

//https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?


public class 删除链表中重复的结点 {
    public ListNode deleteDuplication(ListNode pHead) {
        //合法性判断
        if (pHead == null){
            return null;
        }
        //head:虚拟一个节点把他的下一个连到头节点方便操作
        ListNode head = new ListNode(-1);
        head.next = pHead;
        //pre：开始重复节点的前一个节点
        ListNode pre = head;
        //last：最后重复的节点
        ListNode last = pre.next;
        while (last != null){
            //持续相等和持续不想等的情况都会出现，所以两种情况都需要while进行持续处理
            while (last.next != null && last.next.val != last.val){
                last = last.next;
                pre = pre.next;
            }
            while (last.next != null && last.next.val == last.val){
                last = last.next;
            }
            //两个while走完说明
            // 1、last.next空了但是好(pre,last]是重复元素
            // 2、last.next空了但是pre.next=last说明整个区间只有一个元素即没有重复
            // 3、last.next不空此时(pre,last]肯定限制了重复元素
            if (pre.next != last){
                //这俩不相等只要去重就好了
                pre.next = last.next;
            }
            last = last.next;
        }
        return head.next;
    }

    //题目给定链表
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}