Swift - LeetCode - 重排連結串列
題目
重排連結串列
問題:
給定一個單鏈表 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 }