Leetcode61. 旋转链表

川长思鸟来 2022-01-15 04:01 156阅读 0赞

给定一个链表，旋转链表，将链表每个节点向右移动 *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

思路：刚开始的思路，我就直接想到直接将尾节点链接到首节点，构成一个环，再移动头指针，即可，问题就是移动多少个节点，数学不好的我，硬是花了很久，主要是刚开始思路没有想到直接以环装画出来，这样就直接看到规律移动这些个nums-(k%nums);个节点。但是自己瞎几把弄得 nums+(nums-(k%nums));反而击败了99.87%。

附上代码：

/**
     * 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(k==0)
                return head;
            
            if(head == NULL)
                return NULL;
            
          
            
            ListNode* node = head;
            int nums = 1;
            while(node->next!=NULL){
                nums++;
                node = node->next;
            }
            node->next = head;
            node = head;
            
            
             int length = nums+(nums-(k%nums));
          
            
            int sum = 0;
            while(sum<length-1){
                sum++;
                node = node->next;
            }
            ListNode* find = node->next;
            
            node->next = NULL;
            
            return find;
           
        }
    };