牛客网算法——名企高频面试题143题（14)

合并链表

package 复现代码;

import java.util.ArrayList;

/**
 * @Classname 链表的合并
 * @Description TODO
 * @Date 2020/12/22 15:29
 * @Created by xjl
 */
public class 链表的合并 {

    public class ListNode {
        int val;
        ListNode next;

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

        /**
         * @description TODO 合并链表
         * @param: lists
         * @date: 2020/12/22 15:30
         * @return: 复现代码.链表的合并.ListNode
         * @author: xjl
         */
        public ListNode merge(ArrayList lists) {
            if (lists.size() == 0) {
                return null;
            }
            ListNode res = lists.get(0);
            for (int i = 1; i < lists.size(); i++) {
                res = mergeTwoLists(lists.get(i), res);
            }
            return res;
        }

        private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
            ListNode curr1 = head1;
            ListNode curr2 = head2;

            ListNode res = new ListNode(0);
            ListNode dumpy=res;

            while (curr1 != null && curr2 != null) {
                if (curr1.val > curr2.val) {
                    dumpy.next = curr2;
                    curr2 = curr2.next;
                } else {
                    dumpy.next = curr1;
                    curr1 = curr1.next;
                }
                dumpy = dumpy.next;
            }
            if (curr1 != null) {
                dumpy.next = curr1;
            }
            if (curr2 != null) {
                dumpy.next = curr2;
            }
            return res.next;
        }
    }


    public ListNode mergeKLists(ArrayList lists) {
        if (lists.size() == 0) return null;
        ListNode res = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            res = mergeTwoLists(lists.get(i), res);
        }
        return res;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个新的链表
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 任一为空，直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return pre.next;
    }
}

链表的指定区间翻转

package 复现代码;

/**
 * @Classname 链表的指定翻转
 * @Description TODO
 * @Date 2020/12/22 15:49
 * @Created by xjl
 */
public class 链表的指定翻转 {

    public class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description TODO  第一步是就是的找到的是m-1的位置  然后利用的是的翻转链表的第二种的方式来实现这样样的执行就是的是n-m次就结束
     * @param: head
     * @param: m
     * @param: n
     * @date: 2020/12/22 15:51
     * @return: 复现代码.链表的指定翻转.ListNode
     * @author: xjl
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return head;
        }
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;

        ListNode pre = dumpy;//第一段最后的一个节点
        //找到第m个节点
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;

        for (int i = m; i < n; i++) {
            ListNode future = cur.next;
            cur.next = future.next;
            future.next = pre.next;
            pre.next = future;
        }
        return dumpy.next;
    }
}

无序单链表的排序

package 复现代码;

/**
 * @Classname 无序单链表的排序
 * @Description TODO
 * @Date 2020/12/22 17:34
 * @Created by xjl
 */
public class 无序单链表的排序 {

    public class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description TODO  分割链表采用的快慢指针 第二是合并链表
     * @param: head
     * @date: 2020/12/22 17:36
     * @return: void
     * @author: xjl
     */
    public ListNode sortInList(ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;//一定要设置的head的下一个
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        ListNode head1 = sortInList(head);
        ListNode head2 = sortInList(second);
        ListNode ans = merge(head1, head2);
        return ans;
    }

    /**
     * @description TODO 合并链表
     * @param: head1
     * @param: head2
     * @date: 2020/12/22 18:13
     * @return: 复现代码.无序单链表的排序.ListNode
     * @author: xjl
     */
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode curr1 = head1;
        ListNode curr2 = head2;

        ListNode res = new ListNode(0);
        ListNode dumpy = res;

        while (curr1 != null && curr2 != null) {
            if (curr1.val > curr2.val) {
                dumpy.next = curr2;
                curr2 = curr2.next;
            } else {
                dumpy.next = curr1;
                curr1 = curr1.next;
            }
            dumpy = dumpy.next;
        }
        if (curr1 != null) {
            dumpy.next = curr1;
        }
        if (curr2 != null) {
            dumpy.next = curr2;
        }
        return res.next;
    }
}

约瑟夫问题

package 复现代码;

import java.util.ArrayList;

/**
 * @Classname 环形链表的约瑟夫问题
 * @Description TODO
 * @Date 2020/12/22 18:40
 * @Created by xjl
 */
public class 环形链表的约瑟夫问题 {
    /**
     * @description TODO   约瑟夫问题
     * @param: n
     * @param: m
     * @date: 2020/12/22 18:50
     * @return: int
     * @author: xjl
     */
    public int ysf(int n, int m) {
        //1 通过的链表
        if (n == 0 || m == 0) {
            return -1;
        }
        ArrayList list = new ArrayList();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int removeIndex = 0;
        while (list.size() != 1) {
            removeIndex = (removeIndex + m - 1) % list.size();
            list.remove(removeIndex);
        }
        return list.get(0);

    }

    /**
     * @description TODO   f(n,m)=(f(n-1,m)+m)%n
     * @param: n
     * @param: m
     * @date: 2020/12/22 18:55
     * @return: int
     * @author: xjl
     */
    public int ysf1(int n, int m) {
        //通过的数学公式
        if (n == 0 || m == 0) {
            return -1;
        }
        int last = 0;
        for (int i = 2; i