[C刷考古] 字串反轉、Linked list反轉

1. 字串反轉

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

想法：第一與最後一個交換值，第二個與倒數第二個交換值，以此類推。

C solution

void reverseString(char* s, int sSize){
    void swap(char* a, char* b){
        char tmp = *a;
        *a = *b;
        *b = tmp;
    }
    for(int i=0; i<sSize/2; i++){
        swap(&s[i], &s[sSize-i-1]);
    }
}

Time complexity: O(n). It swaps N/2 times.

Space complexity: O(1). It uses a constant space.

2. Linked list 反轉

Reverse a singly linked list.

//premise
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

想法：

iterative method

recursive method

C iterative method

struct ListNode* reverseList(struct ListNode* head){
    if(!head) return head;
    //prev curr next
    struct ListNode *prev = NULL;
    struct ListNode *curr, *next;
    //loop
    curr = head;
    while(curr){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Time complexity: O(n). Based on the length of the linked list.

Space complexity: O(1). It uses a constant space for the pointers.

C recursive method

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL) return head;
    struct ListNode *prev = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return prev;
}

Time complexity: O(n). Based on the length of the linked list.

Space complexity: O(1). It uses the stack space that is based on the length of the linked list.