2025年- H118-Lc86. 分隔链表(链表)--Java版

1.题目

2.思路

首先维护两个链表，一个链表存储小于x的数，另一个链表存储大于x的数。然后再用小链表的最后一个数指向大链表的第一个数，大链表的最后一个数指向NULL。
创建两个虚拟头结点分别指向小链表的第1个节点和大链表的最后一个节点。
largehead不变的，暂存了大链表的头结点。smallhead不变的，暂存了小链表的头结点

3.代码实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode partition(ListNode head, int x) {ListNode small=new ListNode(0);ListNode smallHead=small;ListNode large=new ListNode(0);ListNode largeHead=large;//如果头结点不为空while(head!=null){if(head.val<x){//小链表虚拟头结点的下一个数指向小链表的头结点small.next=head; //1=1small=small.next;//small=}else{large.next=head;//大链表的虚拟头结点的下一个数 指向大链表的头结点large=large.next;}//如果数顺序排序的，head指针后移head=head.next;}//最后重新链接一下大链表和小链表//大链表的最后一个节点的下一个数指向空large.next=null;//小链表的最后一个结点的下一个数指向大链表的第一个数//largehead不变的，暂存了大链表的头结点small.next=largeHead.next;//返回小链表的第一个数，smallhead不变的，暂存了小链表的头结点return smallHead.next;}
}