首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【链表问题】打卡9:将单链表的每K个节点之间逆序

【链表问题】打卡9:将单链表的每K个节点之间逆序

作者头像
帅地
发布2018-12-27 11:41:58
5610
发布2018-12-27 11:41:58
举报
文章被收录于专栏:苦逼的码农苦逼的码农

前言

以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

注:如果代码排版出现了问题麻烦通知我下,谢谢。

【题目描述】

给定一个单链表的头节点head, 实现一个调整单链表的函数,使得每K个节点之间逆序,如果最后不够K个节点一组,则不调整最后几个节点。

例如:

链表:1->2->3->4->5->6->7->8->null, K = 3。

调整后:3->2->1->6->5->4->7->8->null。其中 7,8不调整,因为不够一组。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉:★★☆☆

【解答】

对于这道题,如果你不知道怎么逆序一个单链表,那么可以看一下我之前写的【链表问题】如何优雅着反转单链表

这道题我们可以用递归来实现,假设方法reverseKNode()的功能是将单链表的每K个节点之间逆序。reverse()方法的功能是将一个单链表逆序。

那么对于下面的这个单链表,其中 K = 3。

我们把前K个节点与后面的节点分割出来:

temp指向的剩余的链表,可以说是原问题的一个子问题。我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。再调用reverse()方法把head指向的那3个节点进行逆序,结果如下:

接着,我们只需要把这两部分给连接起来就可以了。最后的结果如下:

如果不大理解,看下代码可能就比较好理解了。

代码如下

 1//每k个节点为一组的逆转
 2public static Node reverseKNodes(Node head, int k) {
 3    if (head == null || head.next == null) {
 4        return head;
 5    }
 6    Node cur = head;
 7    for (int i = 1; cur != null && i < k; i++) {
 8        cur = cur.next;
 9    }
10    //判断是否能组成一组。
11    if (cur == null) {
12        return head;
13    }
14    //temp指向剩余的链表
15    Node temp = cur.next;
16    cur.next = null;
17    //把k个节点进行反转
18    Node newHead = reverse(head);
19    //把之后的部分链表进行每K个节点逆转转
20    Node newTemp = reverseKNodes(temp, k);
21    //把两部分节点连接起来
22    return newHead;
23}
24
25    //单链表逆序
26public static Node reverse(Node head) {
27    if (head == null || head.next == null) {
28        return head;
29    }
30    Node newHead = reverse(head.next);
31    head.next.next =  head;
32    head.next = null;
33    return newHead;
34}

当然,这道题一个很简单的做法就是利用栈来辅助,每K个节点入栈就把这K个节点出栈连接成一个链表,之后剩余再在进栈…..

不过这种做法的额外空间复杂度是O(K)。

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

本文分享自 帅地玩编程 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 【题目描述】
  • 【要求】
  • 【难度】
  • 【解答】
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档