反转链表的两种方式
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是链表的长度,因为它需要遍历整个链表一次。
总结:
递归方法在代码上看起来更简洁,但迭代方法通常在空间效率上更优,因为递归可能导致堆栈溢出,特别是对于非常长的链表,所以大家在使用时要考虑一下两者哪种更合适。