问题描述
https://leetcode.com/problems/partition-list/
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
//corner case
if(head == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
ListNode left = dummy;
while(cur != null){
if(left == pre){
if(cur.val < x) left = left.next;
pre = pre.next;
cur = cur.next;
}else{
if(cur.val >= x){
pre = pre.next;
cur = cur.next;
}else{
pre.next = cur.next;
cur.next = left.next;
left.next = cur;
cur = pre.next;
left = left.next;
}
}
}
return dummy.next;
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
