南京企业网站设计培训网站

难度中等462收藏分享切换为英文接收动态反馈

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

package 链表;
/** https://leetcode-cn.com/problems/partition-list/* 刚开始想法：* 1. 遍历寻找x最前面的大值max，如果大于3，* 2. 如果 大于3那么位置不变* 3. 如果小于3就放到max的前面* 如果这是数组那就很简单，不过这是链表 * 写到int定义max的想法：* 1. 定义两个列表* 2. 大于3的放在小链表，否则放在大链表* 3. 最后将他们合起来输出就可以了* 我们可以定义两个链表来存储他的小值和大值，最后在合一起*/
public class _86_分隔链表 {public ListNode partition(ListNode head, int x) {
//    	如果链表为空就直接返回或只有一个就直接返回if (head==null||head.next==null) {return head;}
//    	这里定义两个链表ListNode listmin=new ListNode(0);ListNode listmax=new ListNode(0);
//    	定义指针ListNode pivotmin=listmin;ListNode pivotmax=listmax;
//    	循环遍历链表while(head!=null) {
//    		如果<于3,就放到listmin链表里面if (head.val<x) {
//    			这里要写pivotmin.next，不能写pivotmin,因为你要指向下一个pivotmin.next=new ListNode(head.val);pivotmin=pivotmin.next;}else {
//				这里是保存的是大数pivotmax.next=new ListNode(head.val);pivotmax=pivotmax.next;}head=head.next;}
//    	最后将他们合起来,listmax.next加上next是因为要去除第一个零pivotmin.next=listmax.next;return listmin.next;}
}

本人csdn博客：https://blog.csdn.net/weixin_46654114

转载说明：跟我说明，务必注明来源，附带本人博客连接。