力扣刷题笔记-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;
}
}