Thursday, January 20, 2011

Reverse linked list in groups of given size

Sample #1:
k = 3
Input: 1->2->3->4->5->6->7->8->NULL
Output: 3->2->1->6->5->4->8->7->NULL.

Sample #2:
k = 5
Input: 1->2->3->4->5->6->7->80->NULL
Output: 5->4->3->2->1->8->7->6->NULL

// takes head pointer, reverse the list and return new head pointer
NODE* reverse(NODE *head, int k) {
    
    NODE *cur, *prev = NULL, *temp = NULL;    int i;    

    if( head == NULL ) 
        return NULL;
        
    cur = head;
        
    // end of for loop, cur will become the last node
    for( i=0; inext == NULL ) {
            cur->next = prev;
            return cur;
        }
            
        temp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = temp;
    }
 
    head->next = reverse( cur, k );
    return prev;    
}

int main() {

    NODE *head = /* linked list */, *tail;    
    head = reverse( head, 3 );
}



No comments :

Post a Comment