反转链表方法分享

反转链表的两种方式

1.使用递归

struct ListNode* reverseList(struct ListNode* head) {
    if (head==NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newhead=reverseList(head->next);
    head->next->next=head;
    head ->next=NULL;
    return newhead;
}

工作原理：这个函数使用递归来反转链表。它首先递归地反转链表的头节点之后的部分，然后修改当前节点的next指针，使其指向前一个节点。递归的基准情况是当链表为空或只有一个节点时，直接返回头节点。

空间复杂度：O(n)，因为它在递归过程中使用了堆栈空间，堆栈的深度与链表的长度成正比。

时间复杂度：O(n)，其中n是链表的长度，因为它需要遍历整个链表一次。

2.使用迭代

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

工作原理：这个函数使用一个循环来反转链表。它使用三个指针：prev（前一个节点），curr（当前节点），和nextTemp（下一个节点的临时存储）。在每次迭代中，它将当前节点的next指针指向前一个节点，然后更新这三个指针，直到遍历整个链表。

空间复杂度：O(1)，因为它只使用了几个额外的指针，而不依赖于链表的长度。

时间复杂度：O(n)，其中n是链表的长度，因为它需要遍历整个链表一次。

总结：

递归方法在代码上看起来更简洁，但迭代方法通常在空间效率上更优，因为递归可能导致堆栈溢出，特别是对于非常长的链表，所以大家在使用时要考虑一下两者哪种更合适。