題目
環(huán)形鏈表 2
問題:
給定一個鏈表蝙斜，返回鏈表開始入環(huán)的第一個節(jié)點、如果鏈表無環(huán)泌绣、澤返回NULL
說明:
不允許修改給定的鏈表
解題思路:
首先是快慢指針判斷是否有環(huán),判斷完以后钮追，設置一個指針temp指向相遇點并原地循環(huán)一周，再次回到快慢指針相遇的這個結(jié)點時算出這個環(huán)總共包含多少結(jié)點阿迈，結(jié)點數(shù)設為n元媚。然后讓快慢指針都回到head，再讓快指針提前走n步苗沧，然后快慢指針同時每次走一步刊棕，相遇的結(jié)點即為入環(huán)結(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 hasCycleII(_ l1 : SingNode?) -> SingNode? {
if l1 == nil {
return l1
}
var fast = l1
var slow = l1
var nodeCount = 1
var tempNode:SingNode? = nil
while fast?.nextNode != nil && fast?.nextNode?.nextNode != nil {
fast = fast?.nextNode?.nextNode
slow = slow?.nextNode
if fast == slow {
tempNode = slow
break;
}
if fast?.nextNode == nil || fast?.nextNode?.nextNode == nil {
tempNode = nil
}
}
if tempNode != nil {
while tempNode?.nextNode != slow {
tempNode = tempNode?.nextNode
nodeCount += 1
}
slow = l1
fast = l1
for _ in 0..<nodeCount {
fast = fast?.nextNode
}
while slow != fast {
slow = slow?.nextNode
fast = fast?.nextNode
}
return slow
}
return tempNode
}
