抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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
}

看题解吧,很清晰:https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode/

课后题两道:

142. 环形链表 II

25. K 个一组翻转链表


2条评论

发表评论