dummy节点和尾巴插法

给出一个链表和一个数X，要求将链表中所有小于X的值放到左边，等于或者大于X的值放到右边，并且原链表的节点顺序不变。

示例：
假设： 1->7->3->5->2->8->4，给定x=4
那么变换后的节点为： 1->3->2->7->5->8->4

思路：
我们先把题目简单化，我们可以先找出链表中小于X的节点放到一个新的链表里面
然后再找出等于或者大于X的节点放到另外一个条链表
最后将第一条链表的next指向第二条链表的头结点，这样就完成了题目的要求。

代码如下：

class ListNode {
      public var val: Int
      public var next: ListNode?
      public init(_ val: Int) {
          self.val = val
          self.next = nil
      }
  }

class NewSoluction {
    func getNewList(_ l1:ListNode?,x:Int)->ListNode?{
        let headDummy = ListNode(0), tailDummy = ListNode(0)
        var head = headDummy,tail = tailDummy
        var node = l1
        while node != nil {
            if node!.val < x {
                head.next = node!
                head = node!
            }else{
                tail.next = node!
                tail = node!;
            }
            node = node!.next
        }
        tail.next = nil;
        //头链加上尾链
        head.next = tailDummy.next
        return headDummy.next
    }
}

注意：tail.next = nil 是为了防止形成环，因为tail.next = node ! ,tail = node这一句实际上是形成了环，所以需要将tail.next置空来打破环