专栏首页江涛的博客leetcode - 交换链表中的节点

leetcode - 交换链表中的节点

题意

给你链表的头节点 head 和一个整数 k

交换 链表正数第 k 个节点和倒数第 k 个节点的值后,返回链表的头节点(链表 从 1 开始索引)。

示例

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[1,4,3,2,5]

示例 2:

输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]

示例 3:

输入:head = [1], k = 1
输出:[1]

示例 4:

输入:head = [1,2], k = 1
输出:[2,1]

示例 5:

输入:head = [1,2,3], k = 2
输出:[1,2,3]

提示

  • 链表中节点的数目是 n
  • 1 <= k <= n <= 105
  • 0 <= Node.val <= 100

出处

链接:https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list

思路

这题常规的做法是,找到第 k 个节点的上一个节点,然后将其 next 指向倒数第 k 个节点的,再将倒数第 k 个节点的 next 指向第 k 个节点的 next,然后将倒数第 k + 1 节点的 next 指向第 k 个节点,第 k 个节点的 next 节点指向倒数第 k 个节点的 next 节点。是不是有点绕,我倒是有个不成熟的想法,也试着去提交了下,发现能过。就是我把所以的 val 值取出来转数组,在 js 中,单纯的同类型数组,它在内存中是连续的,所以其访问复杂度是 O(1),所以我们把生成的数组的第(k - 1)个 和 数组的长度减去 k 的那位交换。最后我们构造一个新的链表返回,当然啦,后面笔者比较菜用了两次遍历去构造这个链表然后返回。

代码

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const swapNodes = function (head, k) {
  const arr = [];
  while (head.next) {
    arr.push(head.val);
    head = head.next;
  }
  head && arr.push(head.val);
  let tmp = arr[k - 1];
  arr[k - 1] = arr[arr.length - k];
  arr[arr.length - k] = tmp;
  const res = [];
  for (let i = 0; i < arr.length; i++) {
    const node = new ListNode(arr[i]);
    res.push(node);
  }
  for (let i = 0; i < arr.length - 1; i++) {
    res[i].next = res[i + 1];
  }
  return res[0];
};

export default swapNodes;

测试

import ListNode from '../../code/base/list-node';
import swapNodes from '../../code/leetcode/1721';

describe('test function swapNodes: ', () => {
  test('test case head = [1,2,3,4,5], k = 2', () => {
    const before = [1, 2, 3, 4, 5];
    const res_before = [];
    for (let i = 0; i < before.length; i++) {
      const node = new ListNode(before[i]);
      res_before.push(node);
    }
    for (let i = 0; i < before.length - 1; i++) {
      res_before[i].next = res_before[i + 1];
    }
    const after = [1, 4, 3, 2, 5];
    const res_after = [];
    for (let i = 0; i < after.length; i++) {
      const node = new ListNode(after[i]);
      res_after.push(node);
    }
    for (let i = 0; i < after.length - 1; i++) {
      res_after[i].next = res_after[i + 1];
    }
    const res = swapNodes(res_before[0], 2);
    expect(res).toEqual(res_after[0]);
  });
});

思考

  • 请读者思考,用楼上提到的常规解法去求解
  • 请读者思考,如果在笔者的基础上,进一步优化代码

哈哈哈,挖坑不填坑。。。

说明

本文首发于 GitHub 仓库https://github.com/ataola/coding,线上阅读地址:https://zhengjiangtao.cn/coding/,转载请注明出处,谢谢!

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1721. 交换链表中的节点(快慢指针)

    交换 链表正数第 k 个节点和倒数第 k 个节点的值后,返回链表的头节点(链表 从 1 开始索引)。

    Michael阿明
  • LeetCode - 两两交换链表中的节点

    该题是第24题,这题一开始我还想了好一会儿,后来发现,好像这样子就好了。递归真的是能用就用,实在是因为递归写起来简单啊。

    晓痴
  • LeetCode | 24.两两交换链表中的节点

    上面的题就是 两两交换链表中的节点 题目的截图,同时 LeetCode 给出了一个函数的定义,然后要求实现链表两两交换的函数体。函数定义如下:

    码农UP2U
  • LeetCode-24 两两交换链表中的节点

    今天我们学习第24题两两交换链表中的节点,这是一道中等题。像这样链表的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们...

    用户3470542
  • LeetCode 24. 两两交换链表中的节点

    https://leetcode-cn.com/problems/swap-nodes-in-pairs/

    freesan44
  • 【刷穿 LeetCode】24. 两两交换链表中的节点(中等)

    做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。

    宫水三叶的刷题日记
  • LeetCode 24. 两两交换链表中的节点(递归+循环)

    Michael阿明
  • 【手绘漫画】图解LeetCode之两两交换链表中的节点(LeetCode 24)

    我是管小亮
  • 【leetcode刷题】T100-两两交换链表中的节点

    本题交换指针较为复杂,画一个图就较为清楚了。注意:前两个元素交换和其他两个元素交换操作不一样。

    木又AI帮
  • LeetCode题目24:两两交换链表中的节点

    原题链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs

    二环宇少
  • 两两交换链表中的节点

    一份执着✘
  • 两两交换链表中的节点

    通过迭代的方式实现两两交换链表中的节点,直接遍历整个链表即可,首先定义一个空的头结点,之后定义前置节点与当前正需要处理的节点,当正在处理的节点存在以及当前节点的...

    WindrunnerMax
  • Leetcode打卡 | No.24 两两交换链表中的节点

    欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

    小小詹同学
  • 两两交换链表中的节点(leetcode24)

    Vincent-yuan
  • 24. 两两交换链表中的节点

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs 著作权归领扣网络...

    lucifer210
  • 24. 两两交换链表中的节点

    CaesarChang张旭
  • ​LeetCode刷题实战24:两两交换链表中的节点

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 451. 两两交换链表中的节点链表处理

    给一个链表,两两交换其中的节点,然后返回交换后的链表。 样例 给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。 你的算法只能使用常...

    和蔼的zhxing
  • 链表合并与节点交换——LeetCode 第 23&24 题

    今天的两道题目全都围绕链表,第一个是困难级别的、要合并多个排序的链表;第二题是中等难度,需要两两交换链表中的节点,昨天没能用递归法写出代码,今天就尝试用递归实现...

    TTTEED

扫码关注云+社区

领取腾讯云代金券