原题传送门

1. 题目描述

2. Solution 1

1、思路分析
新建两个头结点，left存放小于x的结点，right存放大于等于x的结点值。从head遍历原始链表，结点值小于x挂left，大于等于x挂right，遍历结束后把right挂到left后面。

2、代码实现

package Q0099.Q0086PartitionList;  import DataStructure.ListNode;  public class Solution {     public ListNode partition(ListNode head, int x) {         ListNode left = new ListNode(0);         ListNode right = new ListNode(0);         ListNode l = left;         ListNode r = right;         while (head != null) {             if (head.val < x) {                 l.next = head;                 l = l.next;             } else {                 r.next = head;                 r = r.next;             }             head = head.next;         }         r.next = null;         l.next = right.next;         return left.next;     } } 

3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(1)