算法面试题 | 链表相交 & 成环问题

class Solution {
    fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
        if (null == headA || null == headB) {
            return null
        }
        val set = HashSet<ListNode>()
        var pA = headA
        var pB = headB
        while (null != pA) {
            set.add(pA)
            pA = pA.next
        }
        while (null != pB) {
            if (set.contains(pB)) {
                return pB
            }
            pB = pB.next
        }
        return null
    }
}
复制代码

class Solution {
    fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
        if (null == headA || null == headB) {
            return null
        }
        var pA = headA
        var pB = headB
        while (pA != pB) {
            // 退出的关键是：pA和pB指向同一个指针（不是值相等），或者都指向null
            pA = if (null == pA) headB else pA.next
            pB = if (null == pB) headA else pB.next
        }
        return pA
    }
}
复制代码

class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        val set = HashSet<ListNode>()
        var p = head
        while (null != p) {
            if (set.contains(p)) {
                return true
            }
            set.add(p)
            p = p.next
        }
        return false
    }
}
复制代码

class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        var slow = head
        var fast = head
        while (null != fast && null != fast.next) {
            slow = slow!!.next
            fast = fast.next!!.next
            if (slow == fast) {
                return true
            }
        }
        return false
    }
}
复制代码

class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        // 1. 寻找双指针相交位置
        var slow = head
        var fast = head
        var intersect: ListNode? = null
        while (null != fast && null != fast.next) {
            slow = slow!!.next
            fast = fast.next!!.next
            if (slow == fast) {
                intersect = slow
                break
            }
        }
        // 2. 寻找成环位置
        if (null == intersect) {
            return null
        } else {
            var p = intersect
            var q = head
            while (p != q) {
                p = p!!.next
                q = q!!.next
            }
            return p
        }
    }
}
复制代码

class Solution {
    fun rotateRight(head: ListNode?, k: Int): ListNode? {
        if (null == head || null == head.next || 0 == k) {
            return head
        }
        var cur = head
        // 1. 找到尾节点
        var count = 1
        while (null != cur!!.next) {
            cur = cur.next
            count++
        }
        if (0 == k % count) {
            // 旋转后未变化
            return head
        }
        // 2. 链表成环
        cur.next = head
        // 3. 找到倒数第 k 个节点的前驱节点
        cur = head
        for (index in 0 until count - (k % count) - 1) {
            cur = cur!!.next
        }
        // 4. 断开 preK
        val preK = cur
        val kP = preK!!.next
        preK.next = null
        return kP
    }
}
复制代码

class Solution {
    fun circularArrayLoop(nums: IntArray): Boolean {
        val visits = BooleanArray(nums.size) { false }
        fun isCircle(from: Int): Boolean {
            if (visits[from]) {
                return false
            }
            val set = HashSet<Int>()
            var cur = from
            while (true) {
                // 路径标志
                visits[cur] = true
                val nextIndex = nums.jump(cur)
                if (nums[nextIndex] * nums[cur] < 0) {
                    // 逆向
                    return false
                }
                if (set.contains(cur)) {
                    return cur != nextIndex
                }
                set.add(cur)
                cur = nextIndex
            }
        }
        for (index in 0 until nums.size) {
            if (isCircle(index)) {
                return true
            }
        }
        return false
    }
    /**
     * @return index of next jump
     */
    fun IntArray.jump(curIndex: Int): Int {
        val nextIndex = curIndex + this[curIndex] % size
        if (nextIndex < 0) {
            return size + nextIndex
        }
        if (nextIndex >= size) {
            return nextIndex - size
        }
        return nextIndex
    }
}
复制代码