前端刷题路-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
}
 

回复

我来回复
  • 暂无回复内容