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.

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

Example:

`Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULL`

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

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.