swift创建链表一

给出一个链表和一个值X，要求将链表中所有小于x的值放到左边，所有大于或等于x的值放到右边，并且原链表的节点顺序不能变
例如：1->3->9->6->7->2->9 x = 4
结果：1->3->2->9->6->7->9

class ViewController: UITableViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        let list = List()
        list.trailFun(1)
        list.trailFun(1)
        list.trailFun(3)
        list.trailFun(2)
        list.trailFun(4)
        list.trailFun(2)
        //打印链表
        /*
        while list.head != nil {
            print(list.head?.val)
            list.head = list.head?.next
        }*/
        
        //获取左右链表
        var dummy = getLeftRightList(list.head, x: 3)
        while  dummy != nil{
            print(dummy?.val)
            dummy = dummy?.next
        }
    }
    
    func getLeftRightList(_ head : Node? , x : Int) -> Node? {
        let leftDummy = Node(0)
        let rightDummy = Node(0)
        var node = head
        var leftPDummy = leftDummy
        var rightPDummy = rightDummy
        while node != nil {
            if node!.val < x{
                //左边
                leftPDummy.next = node
                leftPDummy = node!
            }else{
                //右边
                rightPDummy.next = node
                rightPDummy = node!
            }
            node  = node?.next
        }
        //构成环
        rightPDummy.next = nil
        //拼接左右链表
        leftPDummy.next = rightDummy.next
        return leftDummy.next
        
    }
    
    
    
    func getLeftList(_ head : Node? , x : Int) -> Node? {
        let dummy = Node(0)
        var p = dummy , node = head
        while node != nil {
            if node!.val < x{
                p.next = node
                p = node!
            }
            node = node!.next
        }
        p.next = nil
        return dummy.next
    }
    
}
//节点
class Node {
    var val : Int
    var next : Node?
    init(_ val : Int) {
        self.val = val
        self.next = nil
    }
}
class List {
    var head : Node?
    var trail : Node?
    //尾插法
    func trailFun(_ val : Int) -> Void {
        if head == nil{
            head = Node(val)
            trail = head
        }else{
            trail?.next = Node(val)
            trail = trail?.next
        }
    }
    //头插法
    func headFun(_ val :Int) -> Void {
        if trail == nil{
            trail = Node(val)
            head = trail
        }else{
            let node = Node(val)
            node.next = head
            head = node
        }
    }
    
}