143. Reorder List

#### QUESTION:

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

``````Input: head = [1,2,3,4]
Output: [1,4,2,3]
``````

Example 2:

``````Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
``````

Constraints:

``````The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000
``````

#### EXPLANATION:

1. 先进行一个pre的操作, 同时获取到当前的count
2. 对count进行循环, 用flag标记需要从头还是从尾部取
3. 将取出来的放在cur的next, 同时将pre或者last进行移动
4. 最后将cur的next进行去尾操作

#### SOLUTION:

``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
var count:Int = last == nil ? 0 : 1
while ((last?.next) != nil) {
last?.next?.pre = last
last = last?.next
count += 1
}
var flag:Bool = false
while (count > 1) {
if !flag {
cur?.next = last
last = last?.pre
} else {
cur?.next = pre
pre = pre?.next
}
cur = cur?.next
flag = !flag
count -= 1
}
cur?.next = nil
}
}
extension ListNode {

private static var _preMap = [String:ListNode?]()

var pre:ListNode? {
get {
let tmpAddress = String(format: "%p", unsafeBitCast(self, to: Int.self))