图解:如何旋转链表
共 2739字,需浏览 6分钟
·
2020-09-07 04:40
前言
题目:
示例 1:
解释:
向右旋转 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节点后分成两部分。
然后尾节点指向头节点就可以实现链表的旋转。
那么,这道看似旋转的题就很简单了,我们可以将其分为三步:
找到分段节点位置;
从分段节点后断开;
将尾节点指向头节点。
头节点位置是已知的,分段节点位置(位置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;
}
先连接后分段
既然最终会将头节点指向尾节点,我们能不能一开始就把链表首尾相连,找到分段位置,将其断开呢?
那么我们的操作顺序就变为了:
链表首尾相连;
找到分段位置;
从分段节点后断开。
代码实现:
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。
推荐,推荐一个 GitHub,这个 GitHub 整理了几百本常用技术PDF,绝大部分核心的技术书籍都可以在这里找到,GitHub地址:https://github.com/iamshuaidi/CS-Book(电脑打开体验更好),地址阅读原文直达