86 单链表的分解

你说你会改变，但是你只是为了解决当时的冲突而讲的话。

给你一个链表头节点head和x，要求链表中所有小于x的节点都出现在大于或等于x的节点之前

例如：head = [1,4,3,2,5,2], x = 3;

输出：[1,2,2,4,3,5]

在合并两个链表的时候，是将两个链表合并成一个，拆分的时候，是将一个链表拆分成两个。这中间涉及了什么，你知道吗。

这道题的解题思路是使用两个链表，一个用来保存比x小的，一个用来保存比x大的，将原始链表遍历结束之后，小的那个链表的尾指针的next指向大的那个链表的虚拟头指针的next，这样就拼接起来整个链表了。

代码如下：

class Solution {
    /**
     * 思想：
     * 双指针，左指针指向数组最左侧的数据，右指针指向数组结尾
     * 循环结束的出口是两个指针相遇，也就是说这个算法是两个指针的方向不一样
     * 指针移动的条件是，如果左指针指向的数据对应的更高，就是height[left]<hight[right]，左指针右移，反之右指针左移，这样可以保证面积更大
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right){
            int area = Math.min(height[left],height[right]) * (right - left);
            maxArea = Math.max(maxArea,area); // 取最大的

            if (height[left] < height[right]){
                left++;
            } else {
                right--;
            }

        }
        return maxArea;

    }
}