Reversing a Linnked List

Problem: Given the head of a singly linked list, reverse the list and return the new head.

Approach: Iterative Node Reversal

To reverse a linked list iteratively, we can utilize three pointers: current, previous, and temporary. The current pointer traverses the list, while the previous pointer keeps track of the reversed portion. The temporary pointer helps store the next node before we modify the links.

Algorithm Steps

1. Initialize previous pointer as NULL and current pointer at the head of the list
2. Iterate through the list until current becomes NULL
3. In each iteration:
   • Store the next node of current in temporary
   • Reverse the link by pointing current's next to previous
   • Move previous to current
   • Move current to the temporary node (stored next node)
4. Return previous as the new head of the reversed list

Implementation

struct ListNode* reverseLinkedList(struct ListNode* head) {
    struct ListNode* previous = NULL;
    struct ListNode* current = head;
    struct ListNode* next_node = NULL;
    
    while (current != NULL) {
        // Store the next node
        next_node = current->next;
        
        // Reverse the current node's pointer
        current->next = previous;
        
        // Move pointers one position ahead
        previous = current;
        current = next_node;
    }
    
    // Previous is now the new head of the reversed list
    return previous;
}

Rotating an Array

Problem: Given an enteger array nums, rotate the array to the right by k steps, where k is non-negative.

Approach 1: Triple Reversal

This approach leverages the properties of array reversal to achieve rotation with O(n) time complexity and O(1) space complexity.

Algorithm Steps

1. Normalize k by taking modulo with array length to handle cases where k > array length
2. Reverse the first n-k elements of the array
3. Reverse the last k elements of the array
4. Reverse the entire array

Implementation

void reverseArray(int* arr, int start, int end) {
    while (start < end) {
        // Swap elements
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        
        // Move indices
        start++;
        end--;
    }
}

void rotateArray(int* nums, int numsSize, int k) {
    // Handle cases where k is larger than array size
    k = k % numsSize;
    
    // Reverse the first part (0 to n-k-1)
    reverseArray(nums, 0, numsSize - k - 1);
    
    // Reverse the second part (n-k to n-1)
    reverseArray(nums, numsSize - k, numsSize - 1);
    
    // Reverse the entire array
    reverseArray(nums, 0, numsSize - 1);
}

Approach 2: Extra Array Method

This approach uses additional space to store the rotated array and then copies it back to the original array.

Algorithm Steps

1. Normalize k by taking modulo with array length
2. Create a temporary array of the same size
3. Copy the last k elements to the beginning of the temporary array
4. Copy the first n-k elements to the end of the temporary array
5. Copy the temporary array back to the original array

Implementation

void rotateArrayWithExtraSpace(int* nums, int numsSize, int k) {
    // Handle cases where k is larger than array size
    k = k % numsSize;
    
    // Create a temporary array
    int* temp = (int*)malloc(numsSize * sizeof(int));
    
    // Copy the last k elements to the beginning of temp
    for (int i = 0; i < k; i++) {
        temp[i] = nums[numsSize - k + i];
    }
    
    // Copy the first n-k elements to the end of temp
    for (int i = 0; i < numsSize - k; i++) {
        temp[k + i] = nums[i];
    }
    
    // Copy temp back to nums
    for (int i = 0; i < numsSize; i++) {
        nums[i] = temp[i];
    }
    
    // Free the temporary array
    free(temp);
}