题解 | 链表分割

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode s=new ListNode(0);
        ListNode b=new ListNode(0);
        ListNode pre=pHead,p=pHead;
        ListNode s1=s,b1=b;
        while(p!=null){
            if(p.val<x){
                ListNode q=new ListNode(p.val);
                s.next=q;
                s=q;
            }
            else{
                ListNode q=new ListNode(p.val);
                b.next=q;
                b=q;
            }
            p=p.next;
        }
        s.next=b1.next;
        return s1.next;
        
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode pHead, int x) {
        // 边界条件：空链表或单节点直接返回
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        
        // 哑节点，用于处理头节点可能被修改的情况
        ListNode dummy = new ListNode(0);
        dummy.next = pHead;
        
        // pre指向“第一个大于等于x的节点”的前一个节点
        ListNode pre = dummy;
        // 找到第一个大于等于x的节点的前序位置
        while (pre.next != null && pre.next.val < x) {
            pre = pre.next;
        }
        
        // current用于遍历后续节点，prevCurrent是current的前一个节点
        ListNode prevCurrent = pre.next;
        while (prevCurrent != null && prevCurrent.next != null) {
            ListNode current = prevCurrent.next;
            if (current.val < x) {
                // 若current小于x，将其从原位置移除，插入到pre后面
                prevCurrent.next = current.next;  // 移除current
                current.next = pre.next;          // current指向pre的下一个节点
                pre.next = current;               // pre指向current（完成插入）
                pre = current;                    // pre后移，保持插入位置正确
            } else {
                // 若current大于等于x，继续向后遍历
                prevCurrent = prevCurrent.next;
            }
        }
        
        return dummy.next;
    }
}