题目

相交链表

问题:

编写一个程序，找到两个单链表相交的起始节点。

示例:

例如，下面的两个链表：
     
  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
    }