图解:如何旋转链表

苦逼的码农

共 2739字,需浏览 6分钟

 ·

2020-09-07 04:40




作者|莱乌

前言

题目:

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。


示例 1:

输入:1->2->3->4->5->NULL, k = 2
输出:4->5->1->2->3->NULL


解释:

向右旋转 1 步:5->1->2->3->4->NULL

向右旋转 2 步:4->5->1->2->3->NULL


示例 2:

输入:0->1->2->NULL, k = 4

输出:2->0->1->NULL


解释:

向右旋转 1 步:2->0->1->NULL

向右旋转 2 步:1->2->0->NULL

向右旋转 3 步:0->1->2->NULL

向右旋转 4 步:2->0->1->NULL 


画外音:Leetcode第61题,中等/难度,通过率40.6%  !!!

先分段后连接

下图为链表分别向右旋转2、3、4个位置后的情况。



经过观察,我们不难发现:



k=2时, 链表从位置3节点后分成两部分

k=3时, 链表从位置2节点后分成两部分

k=4时, 链表从位置1节点后分成两部分。

然后尾节点指向头节点就可以实现链表的旋转。


那么,这道看似旋转的题就很简单了,我们可以将其分为三步:

  1. 找到分段节点位置;

  2. 从分段节点后断开;

  3. 将尾节点指向头节点。


头节点位置是已知的,分段节点位置(位置3/位置2等)如何获取呢?


根据初始状态图:

位置3节点指向倒数第k=2个节点;

位置2节点指向倒数第k=3个节点;

位置1节点指向倒数第k=4个节点。


《图解:删除链表倒数第N个节点》里提到的前后双指针方法在这里就可以派上用场了。


画外音:为了与Leetcode保持一致,在这里没有使用单链表基础知识里实现的链表结构(主要区别在哨兵节点)。


可能有人发现了,这里的k值都是小于链表长度的。那么当k大于等于链表长度时,如何定位分段节点位置呢?



由上图可以看出:


当k为链表长度的倍数时,链表是维持原状的。当k为非倍数时,分段节点位置为len-(k%len),指向倒数第k%len个节点。


那么问题就迎刃而解了!!!


代码实现:


struct ListNode* rotateRight(struct ListNode* head, int k){
    if (head == NULL || head->next == NULL || k == 0) {
        return head;
    }

    struct ListNode* p,*q,*newHead,*tmp = head;
    int len,i;
    len = i = 0;
    // 求出链表长度
    while (tmp != NULL) {
        tmp = tmp->next;
        len++;
    }

    k = k % len;
    // k为链表长度倍数时旋转后还是原位置
    if (k == 0) {
        return head;
    }
    p = q = (struct ListNode*)malloc(sizeof(struct ListNode));
    p->next = head;
    q->next = head;

    while(i < k) {
        q = q -> next;
        i++;
    }

    while (q->next != NULL) {
        q = q -> next;
        p = p -> next;
    }

    newHead = p->next;
    p->next = NULL;
    q->next = head;

    return newHead;
}

先连接后分段

既然最终会将头节点指向尾节点,我们能不能一开始就把链表首尾相连,找到分段位置,将其断开呢?



那么我们的操作顺序就变为了:

  1. 链表首尾相连;

  2. 找到分段位置;

  3. 从分段节点后断开。


代码实现:


struct ListNode* rotateRight(struct ListNode* head, int k){
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *q,*p = head;
    int len = 1;

    // 求出链表长度
    while (p->next != NULL) {
        p = p->next;
        len++;
    }

    p->next = head;   // 链表首尾相连成环
    p = head;
    k = len - (k % len);
    while (k > 0 && p != NULL) {
        q = p;          // 新尾节点
        p = p->next;    // 新头结点
        k--;
    }

    q->next = NULL;
    return p;
}


其实,这种方式与上边的方法在本质上是没有区别的,只是将首尾相连的操作前置了。不过可以作为一种解题思路。

总结

1、本文中介绍了两种旋转链表的方式:

  • 先分段后连接:将链表先从分段节点后分割开,然后首尾连接起来;

  • 先连接后分段:将链表先首尾连接起来,再从分段节点后分割开。


2、分段节点位置计算方式为len-(k % len),所指向节点位置计算方式为k%len。




读者福利
《程序员内功修炼》第二版强势来袭,汇总了高质量的算法、计算机基础文章并且每一篇文章,要嘛是漫画讲解,要嘛是对话讲解,一步步引导,要嘛是图形并茂,如果你想学习算法,学习计算机基础,那么我决定这份 PDF,一定会让你有所帮助。当然,如果一是一位有那么点迷茫的在校生,相信我的个人经历,可以给你打一份鸡血,让你更好着去寻找自己的目标。

文章整体目录

如何获取

很简单,在我的微信公众号 帅地玩编程 回复 程序员内功修炼 即可获取《程序员内功修炼》第一版和第二版的 PDF。

推荐,推荐一个 GitHub,这个 GitHub 整理了几百本常用技术PDF,绝大部分核心的技术书籍都可以在这里找到,GitHub地址:https://github.com/iamshuaidi/CS-Book(电脑打开体验更好),地址阅读原文直达

浏览 27
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报