题目

奇偶链表

问题:

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

示例:

示例 1：
     
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2：

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

进阶:

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

解题思路:

建立快慢指针，通过这两个指针获得两个列表，

代码：

/**
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 oddEvenList(_ l1:SingNode?) -> SingNode? {
        if l1 == nil || l1?.nextNode == nil {
            return l1
        }
        var pre = l1
        var last = l1?.nextNode
        let temp = last
        while last != nil && last?.nextNode != nil {
            pre?.nextNode = last?.nextNode
            pre = pre?.nextNode
            last?.nextNode = pre?.nextNode
            last = last?.nextNode
        }
        pre?.nextNode = temp
        return l1
    }