86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

// An highlighted block

class Solution {
	
    fun partition(head: ListNode?, x: Int): ListNode? {
        var l1 : ListNode = ListNode(1) //设置哨兵节点
        var root = l1
        l1.next = head 
        var prefix : ListNode ?= null
        while (l1.next != null) {
            if (l1.next.`val` >= x ) {//找出第一个大于等于x的值，prefix指向该值得前一个节点
                if (prefix == null) {
                    prefix = l1 
                }  
                l1 = l1.next
            } else {
                    var temp : ListNode = l1.next ?: break//定义一个temp指向小于X的节点，同时判断l1是否走到链表最后
                    if (prefix == null) {//如果prefix为null，说明还没有找到大于等于x的值，直接向后遍历
                        l1 = l1.next
                        continue
                    }
                    l1.next = l1.next.next ?: null//需要跳过temp节点，因此temp将会移动到前面去
                    if ( prefix != null) {
                        temp.next = prefix.next
                        prefix.next = temp
                        prefix = temp
                    }
                }
        }
        return root.next
    }
}

// An highlighted block

class Solution {
	
    fun partition(head: ListNode?, x: Int): ListNode? {
        var SmallHead : ListNode = ListNode(0)
        var LargeHead : ListNode = ListNode(0)
        var small = SmallHead
        var large = LargeHead
        var index = head
        while (index != null) {
            if (index.`val` < x) {
                small.next = index
                index = index.next
                small = small.next
                small.next = null
            } else {
                large.next = index
                index = index.next
                large = large.next
                large.next = null
            }
        }
        small.next = LargeHead.next
        return SmallHead.next
    }
}