一、字符串反转
给定字符串
Hello, world, 实现将其反转。输出结果dlrow,olleh。
思路：使用两个指针，一个指向字符串首部begin，一个指向字符串尾部end。遍历过程逐渐交换两个指针指向的字符，结束条件begin大于end。
void char_reverse(char * cha) {
// 指向第一个字符
char *begin = cha;
// 指向字符串末尾
char *end = cha + strlen(cha) - 1;
while (begin < end) {
// 交换字符，同时移动指针
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}
二、链表反转
思路：头插法实现链表反转。定义一个新的head指针作为链表的头部指针，定义一个P指针遍历链表，将每次遍历到的元素插入到head指针后。
代码示例：
// 链表反转
struct Node * reverseList(struct Node *head) {
// 定义变量指针，初始化为头结点
struct Node *p = head;
// 反转后的链表头
struct Node *newH = NULL;
while (p != NULL) {
// 记录下一个结点
struct Node *temp = p -> next;
p->next = newH;
// 更新链表头部为当前节点
newH = p;
// 移动P指针
p = temp;
}
return newH;
}
// 构建一个链表
struct Node * constructList(void) {
// 头结点
struct Node *head = NULL;
// 记录当前节点
struct Node *cur = NULL;
for (int i = 0; i < 5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = i;
if (head == NULL) {
head = node;
} else {
cur->next = node;
}
cur = node;
}
return head;
}
// 打印链表
void printList(struct Node *head) {
struct Node *temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}
测试代码：
struct Node *head = constructList();
printList(head);
printf("---------\n");
struct Node *newHead = reverseList(head);
printList(newHead);
输出结果：
node is 0
node is 1
node is 2
node is 3
node is 4
node is 4
node is 3
node is 2
node is 1
node is 0
三、有序数组合并
如何实现两个有序数组合并成新的有序数组。
思路：两个指针分别指向两个有序数组，比较指针所指向的数据大小，将较小的先插入到新的数组中，最后剩余的那个数组合并到新数组末尾。
示例代码：
// 将有序数组a和b的值合并到一个数组result中，且仍保持有序
void mergeSortedArray(int a[], int aLen, int b[], int bLen, int result[]) {
int p = 0; // a 数组标记
int q = 0; // b 数组标记
int i = 0; // 当前存储位标记
// 任意数组结束
while (p < aLen && q < bLen) {
// 将较小的按个插入到新数组中
if (a[p] <= b[q]) {
result[i] = a[p];
p++;
} else {
result[i] = b[q];
q++;
}
i++;
}
// a数组还有剩余
while (p < aLen) {
result[i] = a[p++];
i++;
}
// b数组有剩余
while (q < bLen) {
result[i] = b[q++];
i++;
}
}
测试代码：
void array_mergeSortedTest() {
int a[5] = {1, 3, 4, 5, 9};
int b[6] = {2, 8, 10, 23, 32, 43};
int result[11];
mergeSortedArray(a, 5, b, 6, result);
printf("merge result is ");
for (int i = 0; i < 11; i++) {
printf("%d ", result[i]);
}
}
输出结果：
merge result is 1 2 3 4 5 8 9 10 23 32 43
示例代码仓库地址：Algorithm
