题目

分隔链表

问题:

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

示例:

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

解题思路:

这个题一直把我搞在蒙圈的路上、不知道有没有人和我一样总认为 value =4的节点要放到value =3节点后面。

代码：

/**
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
    }