本文共 4646 字，大约阅读时间需要 15 分钟。

题目描述

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 {
       /*    就是连续K次右移一个    每次右移一个的时候，其实就是重新尾链接到头部，然后找到合适的位置断开，从而更改了链表头、 这个过程如果每次右移都需要找链表尾，就很耗时，会超时    */public:        ListNode* rotateRight(ListNode* head, int k) {
           if(!head)  return head;        //执行K次右移1        while(k){
                head=right_one(head);             k--;        }                   return head;    }    //执行一次右移的操作： 新head=原tail; 新tail=原tail_pre     ListNode* right_one(ListNode* head){
               //遍历一次找链表尾            ListNode* tail=head;            ListNode* tail_pre=head; //链表的倒数第二个指针            while(tail->next!=nullptr)                if(tail->next->next==nullptr)                    tail_pre=tail;                tail=tail->next;                            tail->next=head;  //成环            head=tail;             tail_pre->next=nullptr;  //重新断开            return head;    }};

那就只能空间换时间了，可是还是超时

测试用例：

好卑鄙的测试用例…,但是看到这个测试用例，我突然想到应该用上数学知识

/** * 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 {
       /*    就是连续K次右移一个    每次右移一个的时候，其实就是重新尾链接到头部，然后找到合适的位置断开。    断开后新的head为原来的tail,新的tail为原tail的前驱。为了找到每个tail的前驱，实行空间换时间。设置一个字典{“node”：“node的前驱”}，就可以只执行一次找尾指针的操作了.    */public:    ListNode * tail_pre;    ListNode * tail;    unordered_map
   
      pre_map;    ListNode* rotateRight(ListNode* head, int k) {
           if(!head)  return head;         //遍历一次找链表尾         if(!head->next) return head;         ListNode * pre=head;         tail= head->next;                 while(pre->next!=nullptr){
               pre_map[tail]=pre;            pre=tail;            if(tail->next!=nullptr)                tail=tail->next;        }        pre_map[head]=tail;        //执行K次右移1        while(k){
                head=right_one(head);             k--;        }                   return head;    }    //执行一次右移的操作： 新head=原tail; 新tail=原tail的前驱     ListNode* right_one(ListNode* head){
                          tail->next=head;  //成环            head=tail;             tail=pre_map[tail];            tail->next=nullptr;  //重新断开            return head;    }};
   

时间上100%

class Solution {
       /*   注意K>链表长的时候会存在大量浪费    */public:    ListNode * tail_pre;    ListNode * tail;    unordered_map
   
      pre_map;    int count=0; //链表长度    ListNode* rotateRight(ListNode* head, int k) {
           if(!head)  return head;                  if(!head->next) return head;         //先计算是链表的第几个元素要做表头         ListNode * pre=head;         tail= head->next;         //遍历一次找链表尾         count=1;        while(pre->next!=nullptr){
               pre_map[tail]=pre;            pre=tail;            if(tail->next!=nullptr)                tail=tail->next;            count++;        }        //K        pre_map[head]=tail;        //K
    
     count的时候们就可以缩减K        if(k==count){
               return head;        }        else if(k>count){
               k=k%count;        }         while(k){
                head=right_one(head);             k--;        }                          return head;    }    //执行一次右移的操作： 新head=原tail; 新tail=原tail的前驱     ListNode* right_one(ListNode* head){
                      tail->next=head;  //成环            head=tail;             tail=pre_map[tail];            tail->next=nullptr;  //重新断开                       return head;    }};
    
   

我再优化空间试试…

class Solution {
       /*   继续优化。不再使用字典了    */public:    ListNode * tail;    int count=0; //链表长度    ListNode* rotateRight(ListNode* head, int k) {
           if(!head)  return head;         if(!head->next) return head;         ListNode* cur=head;         while(cur->next){
                count++;             cur=cur->next;         }         tail=cur;         count++;          //不用旋转的情况         if((k%count)==0)                return head;         //需要旋转的情况        k=k%count;  //旋转k次后，head为原链表的倒数第K个节点            //找原链表的倒数第K个节点,也就是整数第count-K+1个节点        //先找到新头节点的前一个节点        ListNode * pre=head;        for(int i=2;i<=count-k;i++)        {
                  pre=pre->next;        }        tail->next=head; //成环        head=pre->next;    //新的头        pre->next=nullptr; //新的尾指针        return head;    }       };

转载地址：http://vifdi.baihongyu.com/