算法问题——链表问题(中等难度)

725. 分隔链表

/**
 * Copyright (C), 2018-2020
 * FileName: splitListToParts725
 * Author:   xjl
 * Date:     2020/8/13 9:00
 * Description: 分个链表
 */
package LinkList;

public class splitListToParts725 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] ans = new ListNode[k];
        //统计链表的长度
        int len = 0;
        ListNode curr = root;
        while (curr != null) {
            len++;
            curr = curr.next;
        }
        //计算有多少组 和多余的个数
        int l = len / k;
        int r = len % k;

        ListNode head = root;
        ListNode pre = null;

        for (int i = 0; i < k; i++, --r) {
            ans[i] = head;
            int part_len = l + (r > 0 ? 1 : 0);
            for (int j = 0; j < part_len; j++) {
                pre = head;
                head = head.next;
            }
            //设置节点断开
            if (pre != null) {
                pre.next = null;
            }
        }
        return ans;
    }
}

86. 分隔链表

   /**
     * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
     * 你应当保留两个分区中每个节点的初始相对位置。
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition1(ListNode head, int x) {
        ListNode curr = head;
        //设置两个新的节点
        ListNode result1 = new ListNode(-1);
        ListNode s1 = result1;

        ListNode result2 = new ListNode(-1);
        ListNode s2 = result2;

        //遍历head的节点
        while (curr != null) {
            if (curr.val < x) {
                s1.next = curr;
                s1 = s1.next;
            } else {
                s2.next = curr;
                s2 = s2.next;
            }
            curr = curr.next;
        }
        //让s1的节点指向s2的下一个
        s1.next = result2.next;
        s2.next = null;
        return result1.next;
    }

面试题 02.04. 分割链表

/**
 * Copyright (C), 2018-2020
 * FileName: partition86
 * Author:   xjl
 * Date:     2020/8/13 9:04
 * Description: 分割链表
 */
package LinkList;

import org.junit.Test;

public class partition86 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
     * 你应当保留两个分区中每个节点的初始相对位置。
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition1(ListNode head, int x) {
        ListNode curr = head;
        //设置两个新的节点
        ListNode result1 = new ListNode(-1);
        ListNode s1 = result1;

        ListNode result2 = new ListNode(-1);
        ListNode s2 = result2;

        //遍历head的节点
        while (curr != null) {
            if (curr.val < x) {
                s1.next = curr;
                s1 = s1.next;
            } else {
                s2.next = curr;
                s2 = s2.next;
            }
            curr = curr.next;
        }
        //让s1的节点指向s2的下一个
        s1.next = result2.next;
        s2.next = null;
        return result1.next;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(4);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(2);
        ListNode s5 = new ListNode(5);
        ListNode s6 = new ListNode(2);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;
        s5.next = s6;

        ListNode listNode = partition1(s1, 3);

    }
}

61. 旋转链表

/**
 * Copyright (C), 2018-2020
 * FileName: rotateRight61
 * Author:   xjl
 * Date:     2020/8/13 9:57
 * Description: 旋转链表
 */
package LinkList;

public class rotateRight61 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 采用的是的慢指针
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        //计算一下链表的长度
        ListNode curr = head;
        int n = 0;
        while (curr != null) {
            n++;
            curr = curr.next;
        }
        //当k的值大于的时候n的时候
        k = k % n;
        if (k == 0) {
            return head;
        }

        //让快的指针走动
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        //让指针都走到最后
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //断开和连接指针
        ListNode nhead = slow.next;
        fast.next = head;
        slow.next = null;
        return nhead;
    }
}

817. 链表组件

/**
 * Copyright (C), 2018-2020
 * FileName: numComponents817
 * Author:   xjl
 * Date:     2020/8/13 13:37
 * Description: 817. 链表组件
 */
package LinkList;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class numComponents817 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public int numComponents(ListNode head, int[] G) {
        List list = new ArrayList();
//        List temp = new ArrayList();
        //存放数组中国的节点
        for (int i = 0; i < G.length; i++) {
            list.add(G[i]);
        }
        int result = 0;
        int flag = 0;
        while (head != null) {
            if (list.contains(head.val)) {
                list.remove((Object) head.val);
                flag = 1;
            } else if (list.isEmpty()) {
                break;
            } else {
                if (flag == 1) {
                    result++;
                    flag = 0;
                }
            }
            head = head.next;
        }
        if (flag == 1) {
            result++;
        }
        return result;
    }

    public int numComponents(ListNode head, int[] G) {
        Set Gset = new HashSet();
        for (int x: G) Gset.add(x);

        ListNode cur = head;
        int ans = 0;

        while (cur != null) {
            if (Gset.contains(cur.val) &&
                    (cur.next == null || !Gset.contains(cur.next.val)))
                ans++;
            cur = cur.next;
        }

        return ans;
    }

    public int numComponents1(ListNode head, int[] G) {
        List list = new ArrayList();
        //存放数组中国的节点
        for (int i = 0; i < G.length; i++) {
            list.add(G[i]);
        }
        int result = 0;
        int flag = 0;

        while (head != null) {
            if (list.contains(head.val)) {
                flag = 1;
            }
            if (flag == 1 && (!list.contains(head.val)||head.next==null)) {
                result++;
                flag = 0;
            }
            head = head.next;
        }
        return result;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(0);
        ListNode s2 = new ListNode(1);
        ListNode s3 = new ListNode(2);
        ListNode s4 = new ListNode(3);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;

        int[] array = {0, 3, 1};

        int i = numComponents1(s1, array);
        System.out.println(i);

    }
}

328. 奇偶链表

/**
 * Copyright (C), 2018-2020
 * FileName: oddEvenList328
 * Author:   xjl
 * Date:     2020/8/13 14:54
 * Description: 328. 奇偶链表
 */
package LinkList;

import org.junit.Test;

public class oddEvenList328 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

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

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

    /**
     * 两种方法就是的将设计两个链表的 然后在最后的串起来
     * 或者是的使用的两个队列的存储奇数和偶数的 然后在所以此遍历就好。
     *
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = new ListNode(-1);
        ListNode event = new ListNode(-1);

        ListNode pre = odd;
        ListNode curr = event;
        int number = 0;
        while (head != null) {
            if (number % 2 == 0) {
                pre.next = head;
                pre = pre.next;
            } else {
                curr.next = head;
                curr = curr.next;
            }
            head = head.next;
            number++;
        }
        pre.next = event.next;
        curr.next = null;
        return odd.next;
    }

    public ListNode oddEvenList2(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenhead = head.next;

        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        //将节点反过来
        odd.next = evenhead;
        return head;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(2);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(4);
        ListNode s5 = new ListNode(5);
        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;
        ListNode listNode = oddEvenList(s1);
        while (listNode != null) {
            System.out.print(listNode.val + "--");
            listNode = listNode.next;
        }
    }

}

面试题 04.03. 特定深度节点链表

/**
 * Copyright (C), 2018-2020
 * FileName: listOfDepth0403
 * Author:   xjl
 * Date:     2020/8/13 15:37
 * Description:
 */
package LinkList;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class listOfDepth0403 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 采用的是的层序遍历
     * 在 对结果做一次的链表的创建
     *
     * @param tree
     * @return
     */

    public ListNode[] listOfDepth(TreeNode tree) {

        //层序遍历
        List result = cengxu(tree);
        ListNode[] ans = new ListNode[result.size()];
        int index = 0;
        //对每一组数据构建新的节点
        for (List list : result) {
            //构建链表
            ListNode head = new ListNode(-1);
            ListNode curr=head;
            for (int i = 0; i < list.size(); i++) {
                curr.next = new ListNode((Integer) list.get(i));
                curr = curr.next;
            }
            ans[index++] = head.next;
        }
        return ans;
    }

    /**
     * 二叉树的层序遍历
     *
     * @param root
     * @return
     */
    private List cengxu(TreeNode root) {
        if(root==null) {
            return new ArrayList();
        }
        List res = new ArrayList();
        LinkedList queue = new LinkedList();
        //将根节点放入队列中，然后不断遍历队列
        queue.add(root);
        while(queue.size()>0) {
            //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
            int size = queue.size();
            ArrayList tmp = new ArrayList();
            //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
            //如果节点的左/右子树不为空，也放入队列中
            for(int i=0;i