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

Hi I am Samuel