题目

环形链表 2

问题:

给定一个链表，返回链表开始入环的第一个节点、如果链表无环、泽返回NULL

说明:

不允许修改给定的链表

解题思路:

首先是快慢指针判断是否有环,判断完以后，设置一个指针temp指向相遇点并原地循环一周，再次回到快慢指针相遇的这个结点时算出这个环总共包含多少结点，结点数设为n。然后让快慢指针都回到head，再让快指针提前走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 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
        
    }