Reverse String

Write a function that takes a string as input and reverse the same.

Example:

Given s = "hello", return "olleh".

Approach: The idea is to swap the last and the first characters till the middle is reached.

1 2 3 4 5 6 7 8 9 10 11

string reverseString(string &s) { int low = 0, high = s.length() - 1; while(low < high){ char t = s[low]; s[low] = s[high]; s[high] = t; low++; high--; } return s; }

Read More

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Approach:  The idea is to traverse the string from both ends while skipping the non-vowels characters from both ends.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

char* reverseVowels(char* s) { int low = 0, high = strlen(s) - 1; char c; while(low < high){ //move forward to skip consonant while(low < strlen(s) && tolower(s[low]) != 'a' && tolower(s[low]) != 'e' && tolower(s[low]) != 'i' && tolower(s[low]) != 'o' && tolower(s[low]) != 'u'){ low++; } //move backward to skip consonant while(low < high && tolower(s[high]) != 'a' && tolower(s[high]) != 'e' && tolower(s[high]) != 'i' && tolower(s[high]) != 'o' && tolower(s[high]) != 'u'){ high--; } if(low < high){ c = s[low]; s[low] = s[high]; s[high] = c; low++; high--; } } return s; }

Read More

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

This problem involves solution to the reverse linked list problem.

Follow up:

Could you do it in O(n) time and O(1) space?

Approach: Reverse the linked list after the middle and see if the first half is equal to the reversed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL){ return true; } ListNode *slow, *fast; slow = head; fast = head; while(fast->next && fast->next->next){ fast = fast->next->next; slow = slow->next; } ListNode *secondHead = slow->next; slow->next = NULL; //reverse second part of the list ListNode *prev = NULL, *curr, *next = secondHead; while(next){ curr = next; next = next->next; curr->next = prev; prev = curr; } //compare two sublists now ListNode *p = curr; ListNode *q = head; while(p){ if(p->val != q->val) return false; p = p->next; q = q->next; } return true; } };

Read More