06 | 面试题：反转一个单链表&判断链表是否有环

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
206. 反转一个单链表

解法一：迭代

时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        head ?: return null
        var prev: ListNode? = null
        var cur = head
        while (cur != null) {
            val next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        }
        return prev
    }
}

思路：比如链表 1 -> 2 -> 3 ->4

每次拿一个节点保存到 cur。

第一次拿 1，将 prev 给到 1 的下一个节点，这时候就是 1 -> null , 将这个结果赋值给 prev。

第二次拿2，将 prev 给到 2 的下一个节点，这时就是 2 -> 1 -> null，将这个结果赋值给 prev。

如此循环。有点绕，debug多看看就好了。

解法二：递归

class Recursion {
    fun reverseList(head: ListNode?): ListNode? {
        head ?: return head
        head.next ?: return head

        val node = reverseList(head.next)
        head.next?.next = head
        head.next = null
        return node
    }
}

思路：假设已经使用递归将 head子节点都反转好了，这时候就只需要反转 head 和 head.next 。head 从头变成了尾，所以 head.next = null 。也是有点绕。

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
24. 两两交换链表中的节点

思路：主要是两两交换，然后注意下位置。

解法一：迭代

class Solution {
    fun swapPairs(head: ListNode?): ListNode? {
        val dummy = ListNode(-1)
        dummy.next = head
        var pre = dummy
        while (pre.next != null) {
            val cur = pre.next

            val first = cur ?: break
            val second = cur.next ?: break
            //swap
            pre.next = second
            first.next = second.next
            second.next = first

            pre = first
        }
        return dummy.next
    }
}

解法二：递归

class Reversion {
    fun swapPairs(head: ListNode?): ListNode? {
        if (head == null || head.next == null) {
            return head
        }
        val next = head.next
        head.next = swapPairs(next?.next)
        next?.next = head
        return next
    }
}

烧脑，直接上题解吧：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/hua-jie-suan-fa-24-liang-liang-jiao-huan-lian-biao/

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
104. 环形链表

解法一：定时循环，无环则会遇到 null，leetcode时间约0.5s （~~不推荐~~ 测试不可行）

解法二：使用 set 存储，每读取一个存储到 set，如果遇到 set 中已经存在的情况，则有环，如果遇到 null 则无环。时间复杂度：循环O(N)， set 查重O(1)，所以是 O(N*1)，空间复杂度：O(N)

注：请勿将 head 赋值到新变量名

fun hasCycle(head: ListNode?): Boolean {
    val set = HashSet<ListNode>()
    var head = head
    while (head != null) {
        if (head in set) {
            return true
        } else {
            set.add(head)
        }
        head = head.next
    }
    return false
}

解法三：快慢指针，快的走两步。慢的走一步，快慢相遇则为有环，快指针遇到 null 则无环，时间复杂度：O(N)，空间复杂度：O(1)

fun hasCycle(head: ListNode?): Boolean {
    if (head == null || head.next == null) {
        return false
    }
    var slow = head
    var fast = head.next
    while (slow !== fast) {
        if (fast == null || fast.next == null) {
            return false
        }
        slow = slow?.next
        fast = fast.next?.next ?: return false
    }
    return true
}