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

想法:

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

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to Automate Backups with Alibaba Cloud Object Storage Service

Some may support you in your quest.

Manipulating DataFrames with Python | Part 2 (Pivoting, Stacking and Melting)

Is your Android or iOS app really stable check these parameters

Introducing the Kin Rewards Engine

Mastering XPATH for Selenium Testers [With Locator CheatSheet]

Alibaba Cloud RPA: Installing and Activating the Client (Part 6)

Creating a Basic Rails CRUD App

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Samuel Liu

Samuel Liu

Hi I am Samuel

More from Medium

TV ePortfolio

The Long Game — Issue #268

Singapore, we have a problem. #SWHAP

Fulfillment vs Attainment.