[数据结构与算法]LeetCode 61. 旋转链表 C++

题目描述

给你一个链表的头节点 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list

解题思路

特判：如果链表为空，直接返回空。
接下来
1.用num记录链表中元素的个数，并且计数到最后一位的时候让链表闭环，首尾相连，并且退出计数循环。
2.因为k是向右移动的位置，所以我们用resNum来记录num-k%num的值，这个表达式算出来的就是移动完之后链表头结点所处的位置。
3.从头结点开始，i=1，进入循环，i要小于resNum+1，用pre记录前一个结点，p记录当前结点。
当退出循环的时候，i=resNum+1，即新的头结点位置
因为当前链表还是一个闭环的，所以此时p前面的结点pre其实就是新链表的最后一个结点，我们直接让pre->next=NULL就完成了断开闭环，称为链表的功能。
4.最后返回新的头结点p即可。

代码

/**
 * 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(head==NULL){//特判：如果链表为空，直接返回空
            return NULL;
        }
        int num=0;  //用来记录链表里面元素的个数
        ListNode* p=head;//移动指针
        while(true){
            num++;//因为前面把链表为空的情况特判了，所以这边第一次进循环可以直接++
            if(p->next==NULL){//如果当前结点的下一个结点为空结点
                p->next=head;//就让他闭环
                break;//并且退出虚幻
            }
            p=p->next;//否则的话就让p后移
        }
        p=head;//移动指针p重新指向头
        int resNum=num-k%num;//这个是往右移动k位之后，新的头结点所处的位置
        ListNode* pre=p;//新的头节点的直接前驱
        for(int i=1;i<1+resNum;i++){//这个循环退出的时候正好p就是新的头节点
            pre=p;//记录直接前驱
            p=p->next;//p后移
        }
        pre->next=NULL;//将前驱结点的直接后继变为NULL之后可以完成把闭环解开成为单链表的功能
        return p;//返回当前新的头节点
    }
};