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

**字串反轉**

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?

想法：

**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.