題目

重排鏈表

問題:

給定一個單鏈表 L：L0→L1→…→Ln-1→Ln ，
將其重新排列后變?yōu)椋?L0→Ln→L1→Ln-1→L2→Ln-2→…

進(jìn)階:

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例:

示例 1：
     
給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.

示例 2：

給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

解題思路:

首先找到兩個鏈表中點(diǎn)的位置，然后從這個中點(diǎn)開始，中點(diǎn)后面的鏈表的節(jié)點(diǎn)反轉(zhuǎn)，然后用一個頭指針指向原始鏈表的頭結(jié)點(diǎn)，再用一個尾指針指向鏈表的尾節(jié)點(diǎn)，然后從兩邊向中間遍歷，在遍歷的過程中，把尾節(jié)點(diǎn)指向的節(jié)點(diǎn)插入到頭指針的節(jié)點(diǎn)后面。

代碼：

/**
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
    }