目录

链表反转

#include <stdio.h>
#include <stdlib.h>

/* 链表节点结构体定义 */
typedef struct node_s {
    int data;
    struct node_s *next;
} node_t;

node_t *create_node(int data) {
    node_t *new_node = malloc(sizeof(node_t));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

/* 添加链表节点到链表中 */
node_t *append(node_t *head, int data) {
    // 示例化一个节点
    node_t* new_node = create_node(data);

    // 链表的第一个节点为空
    if (NULL == head) {
        head = new_node;
    } else {
        // 第一个节点不为空，那么需要循环链表找到当前的最后一个节点（next 为空）
        node_t *current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        // 将新节点添加到当前最后一个节点的 next，作为链表中新的最后节点
        current->next = new_node;
    }
    return head;
}

/* 反转链表 */
node_t *reverse(node_t *head) {
    node_t *prev = NULL;
    node_t *current = head;
    node_t *next = NULL;

    /* 从 head 开始循环链表，直到最后一个节点，进行反转 */
    while (current != NULL) {
        next = current->next;  // 标记 next
        current->next = prev;  // 反转 cur 和 prev
        prev = current;        // 向前移动 prev 到 cur
        current = next;        // 向前移动 cur 到 next
    }
    return prev;  // 最终成为了反转后的第一个节点
}

void print_list(node_t *head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    node_t *head = NULL;
    head = append(head, 1);
    head = append(head, 2);
    head = append(head, 3);
    head = append(head, 4);
    head = append(head, 5);
    printf("Original list: ");
    print_list(head);

    head = reverse(head);
    printf("Reversed list: ");
    print_list(head);

    return 0;
}

链表局部反转

将 10 个节点按照长度 3 为一个区域进行反转。

#include <stdio.h>
#include <stdlib.h>

/* 链表节点结构体定义 */
typedef struct node_s {
    int data;
    struct node_s *next;
} node_t;

node_t *create_node(int data) {
    node_t *new_node = malloc(sizeof(node_t));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

/* 添加链表节点到链表中 */
node_t *append(node_t *head, int data) {
    // 示例化一个节点
    node_t* new_node = create_node(data);

    // 链表的第一个节点为空
    if (NULL == head) {
        head = new_node;
    } else {
        // 第一个节点不为空，那么需要循环链表找到当前的最后一个节点（next 为空）
        node_t *current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        // 将新节点添加到当前最后一个节点的 next，作为链表中新的最后节点
        current->next = new_node;
    }
    return head;
}

/* 区域反转链表 */
node_t *range_reverse(node_t *head, int k) {
    node_t *prev = NULL;
    node_t *current = head;
    node_t *next = NULL;
    int count = 0;

    /* 从 head 开始循环链表，直到区域边界，进行反转 */
    while (current != NULL && count < k) {
        next = current->next;  // 标记 next
        current->next = prev;  // 反转 cur 和 prev
        prev = current;        // 向前移动 prev 到 cur
        current = next;        // 向前移动 cur 到 next
        count++;               // 区域边界累加
    }

    /* 继续下一个区域，直到链表最后一个节点为止。*/
    if (next != NULL) {
        head->next = range_reverse(next, k);   
    }
    return prev;  // 最终成为了反转后的第一个节点
}

void print_list(node_t *head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    node_t *head = NULL;
    head = append(head, 1);
    head = append(head, 2);
    head = append(head, 3);
    head = append(head, 4);
    head = append(head, 5);
    head = append(head, 6);
    head = append(head, 7);
    head = append(head, 8);
    head = append(head, 9);
    head = append(head, 10);
    printf("Original list: ");
    print_list(head);

    head = range_reverse(head, 3);
    printf("Reversed list: ");
    print_list(head);

    return 0;
}
77
78
79
80
81
82
83
84
85
86
87
88