sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

两两交换链表中的节点-24 #51

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

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

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这题本意比较简单,1 -> 2 -> 3 -> 4 的情况下可以定义一个递归的辅助函数 helper,这个辅助函数对于节点和它的下一个节点进行交换,比如 helper(1) 处理 1 -> 2,并且把交换变成 2 -> 1 的尾节点 1next继续指向 helper(3)也就是交换后的 4 -> 3

边界情况在于,如果顺利的作了两两交换,那么交换后我们的函数返回出去的是 交换后的头部节点,但是如果是奇数剩余项的情况下,没办法做交换,那就需要直接返回 原本的头部节点。这个在 helper函数和主函数中都有体现。

let swapPairs = function (head) {
  if (!head) return null
  let helper = function (node) {
    let tempNext = node.next
    if (tempNext) {
      let tempNextNext = node.next.next
      node.next.next = node
      if (tempNextNext) {
        node.next = helper(tempNextNext)
      } else {
        node.next = null
      }
    }
    return tempNext || node
  }

  let res = helper(head)

  return res || head
}
abigmiu commented 2 years ago
function swapPairs(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) {
        return head;
    }
    let nextNode = head.next;
    head.next = swapPairs(nextNode.next);
    nextNode.next = head;
    return nextNode;
};

这是我从评论里看到的最简洁的解法