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:

这道medium的题目还是有一点需要思考的难度的
首先: 我们可以采用3个指针的方法. 一个cur用来往后排. pre和last用来分别指两端. 同时用一个count来计算需要进行组装的次数. 通过次数进行选择组装. 最后再去尾.

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

SOLUTION:

/**
 * Definition for singly-linked list.
 * 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 {
    func reorderList(_ head: ListNode?) {
        var last:ListNode? = head
        var count:Int = last == nil ? 0 : 1
        while ((last?.next) != nil) {
            last?.next?.pre = last
            last = last?.next
            count += 1
        }
        var cur: ListNode? = head
        var pre: ListNode? = head?.next
        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))
            return ListNode._preMap[tmpAddress] ?? nil
        }
        set(newValue) {
            let tmpAddress = String(format: "%p", unsafeBitCast(self, to: Int.self))
            // UIViewController._myComputedProperty[tmpAddress] = newValue
            ListNode._preMap[tmpAddress] = newValue
        }
    }
}
>
--> return <--