題目:以給定值x為基準(zhǔn)將鏈表分割成兩部分，所有小于x的結(jié)點(diǎn)排在大于或等于x的結(jié)點(diǎn)之前
給定一個(gè)鏈表的頭指針 ListNode* pHead，請(qǐng)返回重新排列后的鏈表的頭指針.

解法1

通過(guò)x分割成兩個(gè)前后兩個(gè)鏈表，然后兩個(gè)鏈表進(jìn)行合并.
<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

第一種解決方案，變量太多，而且不容易控制，可以進(jìn)行簡(jiǎn)化為兩個(gè)鏈表的節(jié)點(diǎn)，不過(guò)最后進(jìn)行兩個(gè)合并的時(shí)候需要遍歷前一個(gè)鏈表.
<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的最后節(jié)點(diǎn)
        beforeStart = beforeStart?.next
    }
    
    beforeStart?.next = afterStart
    
    return head
}`</code></pre>

測(cè)試代碼:
<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