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

    }
}

热门相关:看不见的朋友   催眠舞会   淫乱书生   搬进你心里   姑娘今年28