题目

重排链表

问题:

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

进阶:

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

示例 1：
     
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2：

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->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 reorderList(_ l1:SingNode?) -> SingNode? {
        if l1 == nil || l1 == nil  {
            return l1
        }
        
        var p = l1
        var p2 = l1
        
        while p2?.nextNode != nil {
            p = p?.nextNode
            p2 = p2?.nextNode?.nextNode
            if p2 == nil {
                break
            }
        }
        print(p!)

        var pre = p
        var temp:SingNode? = nil
        p = p?.nextNode
        pre?.nextNode = temp
        while(p != nil){
            temp = p?.nextNode;
            p?.nextNode = pre;
            pre = p;
            p = temp;
        }
        
        var end = pre
        var first = l1

        while first != end {
            if first?.nextNode == end {
                break
            }
            
            let temp = end?.nextNode
            end?.nextNode = first?.nextNode
            first?.nextNode = end
            first = end?.nextNode
            end = temp
        }
        return l1
    }