课程： 新浪微博资深大牛全方位剖析 iOS 高级面试

一、字符串反转

给定字符串 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