前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode - 交换链表中的节点

leetcode - 交换链表中的节点

作者头像
江涛学编程
发布2021-01-28 15:32:54
7840
发布2021-01-28 15:32:54
举报
文章被收录于专栏:江涛的博客

题意

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

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

示例

示例 1:

代码语言:javascript
复制
输入:head = [1,2,3,4,5], k = 2
输出:[1,4,3,2,5]

示例 2:

代码语言:javascript
复制
输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]

示例 3:

代码语言:javascript
复制
输入:head = [1], k = 1
输出:[1]

示例 4:

代码语言:javascript
复制
输入:head = [1,2], k = 1
输出:[2,1]

示例 5:

代码语言:javascript
复制
输入: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 的那位交换。最后我们构造一个新的链表返回,当然啦,后面笔者比较菜用了两次遍历去构造这个链表然后返回。

代码

代码语言:javascript
复制
/**
 * @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;

测试

代码语言:javascript
复制
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/,转载请注明出处,谢谢!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-01-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 江涛学编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 示例
    • 示例 1:
      • 示例 2:
        • 示例 3:
          • 示例 4:
            • 示例 5:
            • 提示
            • 出处
            • 思路
            • 代码
            • 测试
            • 思考
            • 说明
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档