题目
分隔链表
问题:
给定一个链表和一个特定值 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
}
