[数据结构与算法]LeetCode每日一题题解：61. 旋转链表-题解-python && C++源代码

61. 旋转链表

难度中等730收藏分享切换为英文接收动态反馈

给你一个链表的头节点?head?，旋转链表，将链表每个节点向右移动?k?个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围?[0, 500]?内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

解题思路：将链表首尾结成环，然后找到新数组的最后一个元素再断开

Python代码：

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or not head or not head.next:#如果 k =0 或者 列表是空列表 或者 列表只有一个数 直接输出列表的值 ，不变
            return head
        n = 1     #n=1 用来求总长度
        ads = head
        while ads.next:  #求出链表的长度
              ads = ads.next
              n += 1
        if (a := n-k%n) == n:  #新链表的最后一个节点（即原链表的第 (n - 1) - (k \bmod n)(n?1)?(kmodn) 个节点，因
            return head
  
        ads.next = head  #因此我们需要接成旋转链表的时候 ，需要再在这里接入

        while a:
            ads = ads.next       #寻找应该断开的地方
            a -= 1
        ret = ads.next
        ads.next = None  #断开
        return ret

C++代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr){//
            return head;
        }
        //当链表长度不大于 11，或者 kk 为 nn 的倍数时，新链表将与原链表相同，我们无需进行任何处理
        int n = 1;  //定义一个n值，用来存放求得的链表的长度
        ListNode*ads = head;  //定义一个ads 用来存放我们之后要形成环的链表
        while(ads->next != nullptr){   //如果ads的下一个不为空，就一直进行while 求得链表的长度
            ads = ads->next;
            n++;
        }
        int a = n-k%n;// 求得们找到新链表的最后一个节点（即原链表的第 (n?1)?(kmodn) 个节点  下一个为要断开的地方 所以这里为 n-k%n
        if (a == n){  //当链表长度为n的倍数的时候，我们直接输出原链表
            return head;   
        }
        ads->next = head;  //将链表结成环
        while (a != 0){
            ads = ads->next;  //找到需要断开的地方
            a -= 1;
        }
        ListNode*dio = ads->next;
        ads->next = nullptr; //断开

        return dio;

    }
};