单链表的逆置（带头结点）

单链表逆置方法1

 使用三个指针时间复杂度：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;
}

单链表逆置方法2

使用两个指针（头插法）
时间复杂度：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;}
}

单链表逆置方法3

用栈实现（使用一个指针）
时间复杂度：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;
}

单链表逆置方法4

递归
时间复杂度：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);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！