旋转链表呵呵

2024-04-13 11:58

文章标签 链表旋转呵呵

本文主要是介绍旋转链表呵呵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、描述

61给定一个链表，旋转链表，将链表每个节点向右移动 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）
链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

链表、旋转

3、思路

首先特判特殊
2、k比链表长度更长
3、快慢指针，节点处理

4、notes&con

first先走，然后用first->next来记录最后，然后调整

5、复杂度

时间：O（N)
空间：O(1)

6、code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(!head||!head->next||k==0)return head;  // 特判auto first=head,second=first;  // 快慢指针int longth=0;while(first)  // 求链表长度{longth++;               first=first->next;                }k%=longth;  // 如果移动的位置比链表还长，first=head;  //first指针重新回到headwhile(k--)  // 让前指针先走k步{first=first->next;}while(first->next)  // 前后指针一起走，当前指针到最后，后指针就是新的结尾{first=first->next;second=second->next;}first->next=head;  // 成串head=second->next;  // 新头指针位置second->next=nullptr;  // 新尾指针置空return head;}  
};