Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
sl1673495 opened this issue May 31, 2020 · 1 comment
Open

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

sl1673495 opened this issue May 31, 2020 · 1 comment
Labels
例题详解 每个分类下会挑出几道题目进行精讲,其他的同类题目会默认拥有这些前置知识而简略讲解。 待复习 看题解或者做出来很艰难的,需要回顾。 链表

Comments

@sl1673495
Copy link
Owner

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

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

示例:

给定 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
}
@sl1673495 sl1673495 added 待复习 看题解或者做出来很艰难的,需要回顾。 链表 labels May 31, 2020
@sl1673495 sl1673495 added the 例题详解 每个分类下会挑出几道题目进行精讲,其他的同类题目会默认拥有这些前置知识而简略讲解。 label Jun 11, 2020
@abigmiu
Copy link

abigmiu commented Aug 29, 2022

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;
};

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
例题详解 每个分类下会挑出几道题目进行精讲,其他的同类题目会默认拥有这些前置知识而简略讲解。 待复习 看题解或者做出来很艰难的,需要回顾。 链表
Projects
None yet
Development

No branches or pull requests

2 participants