103. 环形链表II (reverse-linked-list-ii)

标签

• 链表
• 中等

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：你是否可以使用 O(1) 空间解决此题？

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

基本思路

根据上题-环形链表我们知道两种方式，这题其实思路是一致的，只不是过变体，要求输出入环节点。

同样，我们可以有两种思路 标记 和 快慢指针。

标记太简单，不提了

说下快慢指针的推导

其实我们最主要了解一个隐含等式，快指针走的总长任意时刻都是2: 1的关系

这样：紫色点就是汇合点，快指针已经走完了环的 n 圈，到汇合为止快指针走的 总长度 可以表示为 a + n(b+c) + b

慢指针到汇合为止，走的长度为 a + b，所以快指针隐含两杯关系可表示为 2(a + b)

那么等式就出来了 a + n(b+c) + b = 2(a + b)，注意我们要求的是 a入口

化简就不写了 得 a = c+ (n−1)(b+c)，可以用特殊法，就假设 n = 1，那么 a == c 注意 b + c 是一圈，又回到原点了

写法实现

标记

跟上次一样做标记，当发现第二次走到同样的节点，则说明该节点是环入口。

var detectCycle = function(head) {
    // 这次我们用 set
    const visited = new Set()
    let cur = head;
    while(cur) {
      // 发现走了第二次了，说明就是入口
      if (visited.has(cur)) {
        return cur
      }
      visited.add(cur)
      cur = cur.next
    }
    return null
};

非常简单的思路，但是空间复杂度为 O(n)

快慢指针

var detectCycle = function(head) {
    let [slow, fast, preOther] = [head, head, head];
    while(slow && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            // 新增一个节点从头开始走 当 preOther === slow 时，就是入口
            while(preOther !== slow) {
                slow = slow.next;
                preOther = preOther.next;
            }
            return preOther
        }
    }
    return null
};

这样空间复杂度 O(1)

104. K 个一组翻转链表 (reverse-nodes-in-k-group)

标签

• 链表
• 困难

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶： 你可以设计一个只使用常数额外空间的算法来解决此问题吗？ 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

例1

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

例2

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

基本思想

我们要善于把大问题拆解成简单的小问题。

K 个一组翻转链表 拆分为

• 如何分组
• 如何翻转

这样我们想到上题-翻转链表。是本题的子问题，但由于需要记录长度，稍加改造。

至于按照 k 个一组分组，所以可以使用一个计数器，每次满了 k 个再做下面的翻转操作。然后递归的去处理后面轮数的翻转链表并接上就行。关键是在稿纸上画图。

写法实现

var reverseKGroup = function(head, k) {
  let count = 0, cur = head;
  // 获取本轮的 k 个节点(可能不够)
  while(cur != null && count !== k){
    cur = cur.next;
    count++;
  }
  // 本轮满了 k 个 需要翻转
  if (count === k) {
    // 递归 链接后续 k个反转的链表头节点
    cur = reverseKGroup(cur, k)
    while(count != 0) {
      // 本轮翻转
      [head.next, cur, head] = [cur, head, head.next]
      count--;
    }
    head = cur
  }
  return head
};

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦 点击此处交个朋友 Or 搜索我的微信号infinity_9368，可以聊天说地 加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我 presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考