題目
重排鏈表
問題:
給定一個單鏈表 L：L0→L1→…→Ln-1→Ln 昼钻，
將其重新排列后變?yōu)椋?L0→Ln→L1→Ln-1→L2→Ln-2→…
進(jìn)階:
你不能只是單純的改變節(jié)點內(nèi)部的值扔亥，而是需要實際的進(jìn)行節(jié)點交換苍苞。
示例:
示例 1：
給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.
示例 2：
給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.
解題思路:
首先找到兩個鏈表中點的位置湃交，然后從這個中點開始亏掀，中點后面的鏈表的節(jié)點反轉(zhuǎn)角塑，然后用一個頭指針指向原始鏈表的頭結(jié)點铺遂，再用一個尾指針指向鏈表的尾節(jié)點，然后從兩邊向中間遍歷士袄，在遍歷的過程中悲关，把尾節(jié)點指向的節(jié)點插入到頭指針的節(jié)點后面。
代碼：
/**
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
}
