題目

分隔鏈表

問題:

給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前。你應(yīng)當(dāng)保留兩個分區(qū)中每個節(jié)點的初始相對位置。

示例:

示例 1:     
輸入: head = 1->4->3->2->5->2, x = 3
輸出: 1->2->2->4->3->5

解題思路:

這個題一直把我搞在蒙圈的路上、不知道有沒有人和我一樣總認(rèn)為 value =4的節(jié)點要放到value =3節(jié)點后面。

代碼：

/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}

extension SingNode : CustomStringConvertible {
    public var description: String {
        var string = "\(value)"
        var node = self.nextNode
        
        while node != nil {
            string = string + " -- " + "\(node!.value)"
            node = node?.nextNode
        }
        return string
    }
}
 **/
      
func partition(_ head: SingNode?, _ x: Int) -> SingNode? {
        let prevDummy = SingNode.init(value: 0)
        var prev = prevDummy
        let postDummy = SingNode.init(value: 0)
        var post = postDummy
        
        var node = head

        while node != nil {
            if node!.value < x {
                prev.nextNode = node
                prev = node!
            } else {
                post.nextNode = node
                post = node!
            }
            node = node!.nextNode
        }
        
        post.nextNode = nil
        prev.nextNode = postDummy.nextNode
   
        return prevDummy.nextNode
    }