匿名网友
1. 实现字符串按word逆序，假如字符串”This is Jack”，逆序为”Jack is This”。
解：第一步翻转整个字符串得到”kcaJ si sihT”，第二步翻转字符串中每个单词得到”Jack is This”。
void reverse(char *begin, char *end) {
if (begin == NULL || end == NULL) {
return;
}
while (begin < end) {
// swap *begin and *end
*begin = *begin + *end;
*end = *begin - *end;
*begin = *begin - *end;
begin++;
end--;
}
}
char *reverse_words(char *data) {
// check input
if (data == NULL) {
return NULL;
}
char *begin = data;
char *end = data;
// find the end of the data
while (*end != '\0') {
end++;
}
end = end - 1;
// reverse data
reverse(begin, end);
// reverse word in data
begin = end = data;
while (*begin != '\0') {
if (*begin == ' ') {
begin++;
end++;
} else if (*end == ' ' || *end == '\0') {
reverse(begin, --end);
begin = ++end;
} else {
end++;
}
}
return data;
}
2. 如何判断一个单链表是有环的？
解：设定两个指针slow和fast，slow每次移动一位，fast每次移动2位，如果有环路必定相遇既slow=fast
int is_exist_loop(struct List *head) {
if (head == NULL) {
return 0;
}
struct List *slow = head;
struct List *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return 1;
}
}
return 0;
}
3. 如何逆序单链表
解：将列表的下一个指针分别指向前一个，这里需注意在指正修改之前应该先保存下一个指针。
struct List *reverse_list(struct List *head) {
struct List *new_head = NULL;
struct List *cur = head;
struct List *pre = NULL;
while (cur != NULL) {
struct List *next = cur->next;
if (next == NULL) {
new_head = cur;
}
cur->next = pre;
pre = cur;
cur = next;
}
}
