写文章

前端刷题路-Day4

吐槽君 分类：javascript

两两交换链表中的节点（题号24）

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

链接

leetcode-cn.com/problems/sw…

解释

这一题还好，根据昨天写的反转链表，使用了递归的方法来进行操作，没啥可说的，主要是更好的答案，这里采用的是迭代，反正我是没太看懂，以后有时间可以看看

自己的解法

var swapPairs = function(head) {
  if (!head || !head.next) return head
  var dummy = head.next
  if (dummy.next) dummy.next = swapPairs(dummy.next)
  head.next = dummy.next
  dummy.next = head
  head = dummy
  return head
};

更好的答案

var swapPairs = function(head) {
  // 1. 确认 head 大于等于两个，否则返回;
  if (!head || !head.next) return head;
  // 2. 新建链表哨兵头并创建指针curr；
  let res = new ListNode(null);
  res.next = head;
  let prev = res;
  console.log(prev)
  // 3. 循环开始
  //    3.1 走两步，存为fst, snd;
  //    3.2 哨兵->snd, fst->snd.next, snd->fst;
  //    3.3 推进 curr = curr.next.next;
  while (prev.next && prev.next.next) {
    let [fst, snd] = [prev.next, prev.next.next];
    [prev.next, fst.next, snd.next] = [snd, snd.next, fst];
    prev = prev.next.next;
  }
  // 4. 返回res.next;
  return res.next;
};

环形链表（题号141）

题目

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

  • 你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

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

示例2：

输入：head = [1,2], pos = 0  
输出：true  
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1  
输出：false  
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

链接

leetcode-cn.com/problems/li…

解释

这题首先是想到了一种诡异无比的写法，直接使用JSON.stringify(head)来判断，如果是循环，会报错，然后捕获错误就好，非常简单方便，就是性能堪忧，只能超过5%的人。

第二种解法就比较正常了，使用了迭代的方法，把每个结点的next都存在Map中，之后开始循环，如果Map中已经存在该节点，那就证明已经循环了，直接返回true，碰到null就返回false。

更好的解法其实是双指针迭代，第一种是其实更多的是类似单指针的操作，简单来说就是两个人跑步，一个人先出发，另一个人后触发，如果是一个圈，那么先出发的人必然会遇到后出发的人，也就是它超过第一个人一圈的时候。

第二种更好的解法就是双指针，两个人同时出发，一个人跑的快，一个人跑得慢，是上一种方法的小优化吧，看上去更简洁，运行起来也快一丢丢。

自己的解法1

var hasCycleSpecial = function(head) {
  try {
    JSON.stringify(head)
    return false
  } catch(err) {
    return !!err
  }
};

自己的解法2

var hasCycle = function(head) {
  if (!head || !head.next) return false
  var res = head;
  var obj = new Map
  var ans = false
  while (res) {
    if (obj.has(res)) {
      ans = true
      res = null
    } else {
      obj.set(res, 1)
      res = res.next  
    }
  }
  return ans
};

更好的答案1

var hasCycle = function(head) {
  if (!head || !head.next) return false
  var fast = head.next
  var slow = head
  while (fast !== slow) {
    if (!fast || !fast.next) {
      return false
    }
    fast = fast.next.next
    slow = slow.next
  }
  return true
};

更好的答案2

var hasCycle4 = function (head) {
  var slow = head,
    fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow == fast) return true
  }
  return false
}

回复

我来回复

  • 暂无回复内容