Leetcode 86. 分隔链表

朴灿烈づ我的快乐病毒、 2022-08-28 05:00 84阅读 0赞

## 题目重述 ##

给你一个链表的头节点 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/partition-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

找到第一个大于等于x的节点 往它前面按顺序塞后面碰到的小于x的节点

## Java实现 ##

class Solution {
        
        public ListNode partition(ListNode head, int x) {
        
            // 空和只有一个结点的情况，直接返回即可
            if(head==null || head.next==null){
        
                return head;
            }
            ListNode fakeHead = new ListNode(0,head);
            ListNode pre = fakeHead;
            ListNode q = head;
            // 找到第一个值大于等于x的结点
            while(q!=null && q.val<x){
        
                pre = q;
                q = q.next;
            }
            // 到结束都没找到 
            if(q==null){
        
               return head;
            }
            // 2，1
            ListNode t = q.next;
            ListNode tPre = q;
            while(t!=null){
        
                if(t.val<x){
        
                    tPre.next = t.next;
                    pre.next = t;
                    t.next = q;
                    pre = t;
                    t = tPre.next;
                   
                }else{
        
                    tPre = t;
                    t = t.next;
                }
            }
            return fakeHead.next;
        }
    }