赞
踩
使用三个指针
时间复杂度:O(n)
空间复杂度:O(1)
void ReverseList(LinkList head) { assert(head != NULL); if (head->next == NULL || head->next->next == NULL) { return; } ListNode* pre = NULL, *s = NULL; ListNode* p = head->next; while (p != NULL) { s = p; p = p->next; s->next = pre; pre = s; } head->next = pre; }
使用两个指针(头插法)
时间复杂度:O(n)
空间复杂度:O(1)
void ReverseList(LinkList head) { assert(head != NULL); if (head->next == NULL || head->next->next == NULL) { return; } ListNode* s = NULL, * p = head->next; head->next = NULL; while (p != NULL) { s = p; p = p->next; s->next = head->next; head->next = s; } }
用栈实现(使用一个指针)
时间复杂度:O(n)
空间复杂度:O(n)
void ReverseList(LinkList head) { assert(head != NULL); if (head->next == NULL || head->next->next == NULL) { return; } int len 0; ListNode* p = head->next; while (p != NULL) { len++; p = p->next; } int* stack = (int*)malloc(sizeof(int) * len); int top = -1; p = head->next; while (p != NULL) { top += 1; stack[top] = p->data; p = p->next; } p = head->next; while (p != NULL) { p->data = stack[top]; top = top - 1; p = p->next; } free(stack); stack = NULL; }
递归
时间复杂度:O(n)
空间复杂度:O (n)
ListNode* Reverse(ListNode* p) { if (p == NULL || p->next == NULL) { return p; } ListNode* firstnode = Reverse(p->next); p->next->next = p; p->next = NULL; return firstnode; } void ReverseList(LinkList head) { assert(head != NULL); ListNode* p = head->next; head->next = Reverse(p); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。