ARTS是左耳朵耗子提出来的一个打卡任务。每周一个 Algorithm，Review 一篇英文文章，总结一个工作中的技术 Tip，以及 Share 一个传递价值观的东西！我希望这个事可以给大家得到相应的算法、代码、技术和影响力的训练。



这是我的第三周打卡，标题为“使用图解的方式来解决算法问题”。这周在刷算法的时候，发现对于双指针、引用传递等问题用画图来理解的话，十分容易理解。



Algorithm



奇偶链表

描述：



给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。



请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例：



示例1：



输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL



示例2：



输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

• 应当保持奇数节点和偶数节点的相对顺序。

• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

题解：



这个问题最直接的想法就是双指针思想来构建奇偶链表，然后把偶链表连接在奇链表的尾部。

const oddEvenList = (head) => {
  if (head == null) {
    return null
  }
  let odd = head, even = head.next, evenHead = even;
  while (even != null && even.next != null) {
    odd.next = even.next
    odd = odd.next
    even.next = odd.next
    even = even.next
  }
  odd.next = evenHead
  return head
};



时间复杂度：O(n)

Review



Adding pipelines to JavaScript



ES2019的提案状态有两个新语法：可选链和管道语法。这篇文章主要讲的是管道语法在JavaScript中的使用。



管道操作可以使某些类型的操作变得真正易于阅读，可以举个例子直观地感受到。



//传统方式
const capitalize = (input) => input[0].toUpperCase() + input.substring(1)
const removeSpaces = (input) => input.trim()
const repeat = (input, times) => input.repeat(times)
const withoutPipe = repeat(capitalize(removeSpaces('  i am gods  ')), 2)
console.log(withoutPipe)
//使用管道运算符
const withPipe = '  i am gods  '
  |> removeSpaces
  |> capitalize
  |> (str => repeat(str, 2))
console.log(withPipe)



上面的例子是对一个字符进行各种转换操作，可以看到使用管道语法后大大地减少嵌套括号的数量，阅读起来十分方便。之前在函数式编程语言 Elixir 中接触到管道操作符，在TC39提案中发现 JavaScript 也开始支持管道操作，觉得这个特性很棒。个人觉得，管道语法结合箭头函数可以在未来给 JavaScript 带来更多灵活地运用。



有一点需要注意的是，对多参数的使用发现没有像 Elixir 那样直接。如果有一个期望是两个参数的函数，则需要将其包装在一个箭头函数里。另一种方法可以使用函数柯里化来实现，如下：



const repeat = times => input => input.repeat(times)
const withPipe = '  i am gods  '
  |> removeSpaces
  |> capitalize
  |> repeat(2)

这种写法比上面就更加简洁一些了。



另外，在TC39提案的建议里，有两种新的管道模式：smart pipeline 和 F# pipeline





F# pipeline建议十分接近简单管道，唯一的区别是允许在管道操作中使用 await 来支持异步操作



url
|> fetch
|> await
|> (res => res.json())
|> doSomeJsonOperations



smart pipeline 是借鉴 Hack 语言的。管道的输出被放到一个 # 的 token 中，以供管道右侧的表达式使用。



// With smart pipes
"   string" 
|> toUpper
|> # + " 😎"
|> prepend("😎 ", #)
// Without pipes
prepend(
  "😎 ",
  toUpper("  string") + " 😎"
)



这种方式增加了额外的语法糖，感觉理解起来没有前两种方式直接。

Tip



ssh免密登录



在开发过程中，经常要连接到远程服务器。之前在windows下开发，使用 secureCRT 这样的软件来连接到远程主机，可以记住密码。后来换到mac环境，直接在终端中用 ssh 命令去连接，比较方便，但每次都需要手动输入密码。



于是配置了下ssh的免密登录。原理和操作都十分简单，主要是利用 ssh-copy-id 命令把ssh-key的公钥上传到远程服务器来进行认证。



1. 生成秘钥



cd ~/.ssh
ssh-keygen



2. 使用 ssh-copy-id 复制到远程主机



ssh-copy-id -i .ssh/id_rsa.pub  root@192.168.0.100



3. 免密登录



ssh root@192.168.0.100



Share



分享文章：使用图解的方式来解决算法问题



这周在刷奇偶链表这个算法的时候，发现把链表画出来，通过图解的方式去写算法不到1分钟就可以写完，而且没有错误。官方的题解里也说到“解决链表问题最好的办法是在脑中或者纸上把链表画出来”。有时通过这种方式比看代码要更容易理解。