Clean C solution


  • 0
    K
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode* reverse(struct ListNode* head) {
        struct ListNode* t = head, *prev = 0;
        while(head){
            t = head;
            head = head->next;
        
            t->next = prev;
            prev = t;
        }
        return t;
    }
    int len(struct ListNode* head){
        int c = 0;
        while(head){
            c++;
            head = head->next;
        }
        return c;
    }
    struct ListNode* advance(struct ListNode *head, int n){
        for (int i = 0; i < n && head; i++){
            head = head->next;
        }
        return head;
    }
    
    // rotate could be implemented as 3 reverse, e.g: 1234abc -> 1234(cba) ->  (abc4321) -> abc(1234)
    struct ListNode* rotateRight(struct ListNode* head, int k) {
        struct ListNode* t;
        int n = len(head);
        if (!head || k % n == 0) {
            return head;
        }
    
        t = advance(head, n - k % n - 1); // find t where t->next is a list with exactly n - k nodes
        t->next = reverse(t->next); // reverse the tailing n-k nodes, remember to connect it back to the original list
    
        head = reverse(head); // reverse all nodes
    
        t = advance(head, k % n - 1); // find t where t->next is a list with exactly k nodes
        t->next = reverse(t->next); // reverse the tailing k nodes, and connect it back
    
        return head;
    }
    

    Please note that the above implementation runs 4 pass but seems a little bit clear than the following implementation, which takes 3 + k/n pass.

    // rotate could be implemented as 3 reverse, e.g: 1234abc -> (cba4321) -> (abc)(1234)
    struct ListNode* rotateRight(struct ListNode* head, int k) {
        struct ListNode* t, *t2;
        int n = len(head);
    
        if (!head || k % n == 0) {
            return head;
        }
    
        k %= n;
    
        // step 1: reverse whole list 
        head = reverse(head);
    
        // step 2: find the split position 
        t = advance(head, k - 1);
        t2 = t->next; // t2 is the head of the 
        t->next = 0; // cut into two parts
    
        // step 3: reverse the two parts
        t = head;
        head = reverse(t);
        t->next = reverse(t2); // and connect them again
    
        return head;
    }

Log in to reply
 

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