My sample C++ solution.


  • 0
    L
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    // two condition 1. len >= k, 2 len < k
    //save last k node pointer, O(n)
    class Solution {
        
        void savePoint(ListNode *&p1, ListNode *&p2, ListNode *p, size_t len, int k) {
            if (len <= k+1) {
                p2 = p;
                return;
            }
            
            p1 = p1->next;
            p2 = p;
        }
        
        ListNode* getPoint(ListNode *p1, ListNode* p2, size_t i) {
            vector<ListNode*> v;
            ListNode *curr = p1;
            do {
                v.push_back(curr);
                curr = curr->next;
            } while (curr != p2);
            v.push_back(p2);
            
            return *(v.rbegin()+i);
        }
        
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            if (k == 0 || head == NULL)
                return head;
            
            list<ListNode*> save;
            ListNode *curr = head;
            ListNode *tail = NULL;
            ListNode *p1=head, *p2=head;
            size_t len=0;
            while (curr != NULL) {
                tail = curr;
                ++len;
                savePoint(p1,p2, curr, len, k);
                curr = curr->next;
            }
            
            if (len == k || len == 1)
                return head;
            
            size_t i;
            if (len < k) {
                i = k % len;
                if (i == 0)
                    return head;
    
            } else {
                i = k;
            }
            //len > k;
           ListNode *newT = getPoint(p1,p2, i);
                ListNode *newH = newT->next;
                tail->next = head;
                newT->next = NULL;
                return newH;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.