题解 | #牛群分隔#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param x int整型
     * @return ListNode类
     */
    public ListNode cow_partition(ListNode head, int x) {
        // 用于存放小于x的节点值
        ArrayList<Integer> list1 = new ArrayList<>();
        // 用于存放大于等于x的节点值
        ArrayList<Integer> list2 = new ArrayList<>();

        ListNode temp = head;
        while (temp != null) {
            if (temp.val < x) {
                list1.add(temp.val);
            } else {
                list2.add(temp.val);
            }
            temp = temp.next;
        }
        ListNode cur = new ListNode(-1);
        ListNode result = cur;
        for (int i = 0; i < list1.size(); i++) {
            ListNode node = new ListNode(list1.get(i));
            cur.next = node;
            cur = cur.next;
        }
        for (int i = 0; i < list2.size(); i++) {
            ListNode node = new ListNode(list2.get(i));
            cur.next = node;
            cur = cur.next;
        }
        return result.next;
    }
}

本题知识点分析：

1.集合存取

2.链表遍历和取值

3.链表前驱结点和后继接单

4.链表连接

本题解题思路分析：

1.先将全有的值取出放到集合

2.小于的放入集合1，大于等于的值放入集合2

3.然后将值重新拼接，先拼接集合1，再拼接集合2

4.最后返回虚拟头结点的.next

做完本题我发现可以直接创建两个链表，一次遍历，小于的放在链表1，小于放在链表2，然后让链表1的尾巴指向链表2的头就可以了，这样一次遍历肯定是更快的，推荐直接一次遍历。

本题使用编程语言: Java

如果您觉得本篇文章对您有帮助的话，可以点个赞支持一下，感谢~