题目:以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针.

解法1

通过x分割成两个前后两个链表，然后两个链表进行合并.
<pre><code>` func partitionListNode(node:ListNode,x:Int) -> ListNode {

    var beforeStart:ListNode?
    var beforeEnd:ListNode?
    
    var afterStart:ListNode?
    var afterEnd:ListNode?
    
    var listNode:ListNode? = node
    
    while listNode != nil {
        let next:ListNode? = listNode?.next
        
        let value:Int = Int((listNode?.value)!)!
        
        if value < x {
            if beforeStart == nil { // 插入beforeStart之后
                beforeStart = listNode
                beforeEnd = listNode
            } else {
                beforeEnd?.next = listNode
                beforeEnd = listNode
            }
        } else {
            if afterStart == nil { // 插入afterStart之后
                afterStart = listNode
                afterEnd = listNode
            } else {
                afterEnd?.next = listNode
                afterEnd = listNode
            }
        }
        listNode = next
    }
    
    if beforeStart == nil {
        return afterStart!
    }
    
    beforeEnd?.next = afterStart
    
    return beforeStart!
}`</code></pre>

解法2

第一种解决方案，变量太多，而且不容易控制，可以进行简化为两个链表的节点，不过最后进行两个合并的时候需要遍历前一个链表.
<pre><code>` func partitionListNode2(node:ListNode,x:Int) -> ListNode {

    var beforeStart:ListNode?
    var afterStart:ListNode?
    
    var listNode:ListNode? = node
    
    while listNode != nil {
        let next:ListNode? = listNode?.next
        let value:Int = Int((listNode?.value)!)!
        
        if value < x {
            listNode?.next = beforeStart
            beforeStart = listNode
        } else {
            listNode?.next = afterStart
            afterStart = listNode
        }
        
        listNode = next
    }
    
    if beforeStart == nil {
        return afterStart!
    }
    
    
    let head:ListNode = beforeStart!
    
    while beforeStart?.next != nil { // 找到beforeStart的最后节点
        beforeStart = beforeStart?.next
    }
    
    beforeStart?.next = afterStart
    
    return head
}`</code></pre>

测试代码:
<pre><code>`listNodeManger.headNode = nil

listNodeManger.appendToTail(value: "(1)")
listNodeManger.appendToTail(value: "(3)")
listNodeManger.appendToTail(value: "(5)")
listNodeManger.appendToTail(value: "(2)")
listNodeManger.appendToTail(value: "(4)")
listNodeManger.appendToTail(value: "(6)")
listNodeManger.appendToTail(value: "(8)")
listNodeManger.appendToTail(value: "(7)")
listNodeManger.appendToTail(value: "(9)")

listNodeManger.printListNode(headNode: listNodeManger.headNode!)
print("FlyElephant--链表切分1")
var partitionHeadNode:ListNode = listNodeManger.partitionListNode(node: listNodeManger.headNode!, x: 5)
listNodeManger.printListNode(headNode: partitionHeadNode)
print("FlyElephant--链表切分2")
partitionHeadNode = listNodeManger.partitionListNode2(node: listNodeManger.headNode!, x: 5)
listNodeManger.printListNode(headNode: partitionHeadNode)`</code></pre>

FlyElephant.png