题目:输入两个链表,找出它们的第一个公共节点.
核心代码:
<pre><code>`
func findFirstCommon(firstHead:ListNode?,nextHead:ListNode?) -> ListNode? {
if firstHead == nil || nextHead == nil {
return nil
}
var commonNode:ListNode?
let firstlen:Int = listNodeLength(node: firstHead)
let nextlen:Int = listNodeLength(node: nextHead)
var firstTempNode:ListNode? = firstHead
var nextTempNode:ListNode? = nextHead
let gap:Int = abs(nextlen - firstlen)
var count:Int = 0
if firstlen > nextlen {
while firstTempNode != nil && count < gap {
count += 1
firstTempNode = firstTempNode?.next
}
} else {
while nextTempNode != nil && count < gap {
count += 1
nextTempNode = nextTempNode?.next
}
}
while firstTempNode != nil && nextTempNode != nil {
let value1:Int = firstTempNode!.value!
let value2:Int = nextTempNode!.value!
if value1 == value2 {
commonNode = firstTempNode
break
}
firstTempNode = firstTempNode?.next
nextTempNode = nextTempNode?.next
}
return commonNode
}
func listNodeLength(node:ListNode?) -> Int {
if node == nil {
return 0
}
var count:Int = 0
var tempNode:ListNode? = node
while tempNode != nil {
count += 1
tempNode = tempNode?.next
}
return count
}`</code></pre>
测试代码:
<pre><code>`
var firstSearchNode:ListNode?
var firstSearchHead:ListNode?
searchNode.createList(&firstSearchNode, data: 1)
firstSearchHead = firstSearchNode
searchNode.createList(&firstSearchNode, data: 2)
searchNode.createList(&firstSearchNode, data: 3)
searchNode.createList(&firstSearchNode, data: 6)
searchNode.createList(&firstSearchNode, data: 7)
var nextSearchNode:ListNode?
var nextSearchHead:ListNode?
searchNode.createList(&nextSearchNode, data: 4)
nextSearchHead = nextSearchNode
searchNode.createList(&nextSearchNode, data: 5)
searchNode.createList(&nextSearchNode, data: 6)
searchNode.createList(&nextSearchNode, data: 7)
searchNode.printList(nextSearchHead)
var commonNode:ListNode? = searchNode.findFirstCommon(firstHead: firstSearchHead, nextHead: nextSearchHead)
if commonNode == nil {
print("没有公共节点")
} else {
print("第一个公共节点的值-(commonNode!.value!)")
}`</code></pre>