Swift - LeetCode - 相交連結串列
題目
相交連結串列
問題:
編寫一個程式,找到兩個單鏈表相交的起始節點。
示例:
例如,下面的兩個連結串列: A:a1 → a2 ↘ c1 → c2 → c3 ↗ B:b1 → b2 → b3 在節點 c1 開始相交。
說明:
如果兩個連結串列沒有交點,返回 null.
在返回結果後,兩個連結串列仍須保持原有的結構。
可假定整個連結串列結構中沒有迴圈。
程式儘量滿足 O(n) 時間複雜度,且僅用 O(1) 記憶體。
解題思路:
把a、b連結串列弄成等長,然後一起遍歷,最先相等的結點就是交點。
程式碼:
/** 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 findNodeLength(_ l1 :SingNode?) -> Int { var len = 0 var next = l1 while next != nil { next = next?.nextNode len = len + 1 } return len } **/ func getIntersectionNode(_ l1 :SingNode?, _ l2:SingNode?) -> SingNode? { var len1 = findNodeLength(l1) var len2 = findNodeLength(l2) var head1 = l1 var head2 = l2 while len1 < len2 { head2 = head2?.nextNode len2 = len2 - 1 } while len1 > len2 { head1 = head1?.nextNode len1 = len1 - 1 } while head1 != head2 { head1 = head1?.nextNode head2 = head2?.nextNode } return head1 }