用两种非递归方法以O(N)的时间复杂度，实现反转一个单链表。c语言实现

可以使用双指针迭代法和栈的方法来实现单链表的反转。

- 双指针迭代法：

这种方法通过双指针不断进行遍历并翻转指针的指向来实现单链表的反转。

具体实现如下：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *cur = head, *next = NULL;
    
    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    
    return prev;
}

- 栈的方法：

这种方法通过将单链表的节点依次压栈，在出栈的过程中重新连接各个节点从而实现单链表的反转。

具体实现如下：

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct ListNode *cur = head;
    struct StackNode *top = NULL;
    
    while (cur != NULL) {
        push(&top, cur);
        cur = cur->next;
    }
    
    cur = pop(&top);
    head = cur;
    
    while (top != NULL) {
        cur->next = pop(&top);
        cur = cur->next;
    }
    
    cur->next = NULL;
    
    return head;
}

其中，push和pop函数实现如下：

struct StackNode {
    struct ListNode *node;
    struct StackNode *next;
};

void push(struct StackNode **top, struct ListNode *node) {
    struct StackNode *newNode = (struct StackNode *)malloc(sizeof(struct StackNode));
    newNode->node = node;
    newNode->next = *top;
    *top = newNode;
}

struct ListNode* pop(struct StackNode **top) {
    struct ListNode *node = (*top)->node;
    struct StackNode *temp = *top;
    *top = (*top)->next;
    free(temp);
    return node;
}

以上两种方法的时间复杂度均为O(N)，空间复杂度为O(1)和O(N)。