LeetCode- 86 -分隔链表 – Java – 细喔

云惠网小编 2021年12月26日09:19:24
评论
963字阅读3分12秒
摘要

文章目录题目解题思维代码附图题目这个题目中的 “分隔”并不是真正意义上分隔,将一个链表分隔成两个链表。而是说 以一个整形数据x,让链表以 val 和 x 之间的大小差距进行数组分隔,val值小于x的节点,位于左边,大于和等于则位于整个链表的右边。而且还有一个要求: 不能是 “无序的”,按照原有相对位置。什么意思呢?假设 x == 3 , 第一个 节点的值 是 1,小于x值,而且本身就位于左边,我们就不用去移动它的位置了。这就是题目中 的 保留每个节点的初识相对位置,再换一个说法 : 看到上面

广告也精彩

这个题目中的 “分隔”并不是真正意义上分隔,将一个链表分隔成两个链表。
而是说 以一个整形数据x,让链表以 val 和 x 之间的大小差距进行数组分隔,val值小于x的节点,位于左边,大于和等于则位于整个链表的右边。
而且还有一个要求: 不能是 “无序的”,按照原有相对位置。
什么意思呢?假设 x == 3 , 第一个 节点的值 是 1,小于x值,而且本身就位于左边,我们就不用去移动它的位置了。这就是题目中 的 保留每个节点的初识相对位置,
再换一个说法 : 看到上面那个图中的 val 为 2 的节点没?它 和 val值为1的节点 ,val值都小于 x值(3),位于 链表的左边,但是由于它原先就位于 1 的右边,那么“分隔”后的结果 这个2节点 应该在 1 节点的后面。
这就是 保留 每个节点的初识相对位置。

在这里插入图片描述

附图

解题思维



建立 两个傀儡头节点 small 和 large,small 用来连接 val 值小于x的节点,large 用来连接 val 值大于或等于的节点。
再为 small 和 large 两个头节点创建2个替身变量 smallHead 和 largeHead,让它们记住small 和 large 的头节点的位置,让small 和 large 去 连接/遍历 各自的链表。(嗯。好像对 small 和 large 不厚道,谁让新建的两个节点引用带个 头head 呢? 嗯 ,没错!是这样的。)
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码

class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode();
ListNode smallHead =  small;
ListNode large = new ListNode();
ListNode largeHead = 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 = largeHead.next;
return smallHead.next;
}
}

题目

文章目录

  • 题目
  • 解题思维
  • 代码
    • 附图

本文转自 https://blog.csdn.net/DarkAndGrey/article/details/122137412

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论