题解 | #牛群分隔#

1. 题目考察的知识点

链表的基本操作，双指针

2. 题目解答方法的文字分析

维护两个链表 small 和 large，small链表按顺序存储所有小于 x的节点，large链表按顺序存储所有大于等于 x 的节点。遍历完原链表后，我们只要将 small链表尾节点指向 large链表的头节点即能完成对链表的分隔。sHead 和 lHead分别为两个链表的哨兵结点，即它们的 next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。同时设 small 和 large节点指向当前链表的末尾节点。开始时 sHead=small,lHead=large。随后，从前往后遍历链表，判断当前链表的节点值是否小于 x，如果小于就将 small 的 next指针指向该节点，否则将 large的 next指针指向该节点。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

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) {
        ListNode small = new ListNode(0);
        ListNode sHead = small;
        ListNode large = new ListNode(0);
        ListNode lHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = lHead.next;
        return sHead.next;
    }
}