数据结构 求将单链表逆置的的时间复杂度 详细解释 高手来

数据结构单链表逆置求详细解答~

算法利用的是链表的头插入法，结果是与插入次序正好颠倒
//这是有表头结点链表的逆置
if (head == NULL)//链表为空就退出
return;
struct node *p = head->next, *pnext = NULL;//p是链表当前结点，pnext指向p的后继结点
head->next = NULL;//断开表头结点和后面链表结点的联系
while (p != NULL)
{//如果后面链表中还有结点
pnext = p->next;//pnext暂存当前结点后继结点的指针
p->next = head->next;//将后面链表的第一个结点插入在前面链表的头部
head->next = p;
p = pnext;// p重新指向后面链表的第一结点
}

C

首先，观察最内层赋值语句，发现可简单视为时间复杂度为O(1)的函数f(i,j)
第二层循环次数为n-i+1
第一层循环次数为n
嵌套循环两者次数为乘法，故上界为O(n^2)

其时间复杂度是O(n)，n是链表结点的个数，逆置时，其算法思想是将原表中的结点循着链依次摘下并插入到新表的表头，因此算法中while循环将执行n趟，然后根据算法我们来计算T(n)， T(n)=2+4*n+1+1。解释一下这个算式的由来，2是指while循环前的两个基本操作，4*n是while循环执行n趟，每趟循环中循环体内有3个基本操作和1次循环判断操作，接下来的两个1，前一个1表示最后一趟循环之后还需进行1次循环判断，后一个1是指return操作。因此T(n)=4n+4， 则O(T(n))=O(4n+4)=O(4n)=O(n)。

---

宝塔区17569777706： 数据结构单链表逆置求详细解答 - ？
督芬赐尔： 算法利用的是链表的头插入法,结果是与插入次序正好颠倒 //这是有表头结点链表的逆置 if (head == NULL)//链表为空就退出 return; struct node *p = head->next, *pnext = NULL;//p是链表当前结点,pnext指向p的后继结点 head->next = NULL;//断...

宝塔区17569777706： 一个数据结构的问题,单链表原地逆置,他的算法怎么写啊 ??? - ？
督芬赐尔： Status reverse(LinkList &L) { //L指向单链表的表头,算法将单链表逆转,L指向逆转后的表头.if (L==NULL ) return OK;else if (L->next ==NULL) return OK;p=L; q = p->next; L->next = NULL;while (q!=NULL){Lnode * tem = q ->next; q ->next = p; p = q; q = temp;}L = p;return OK; } 你看怎么样?

宝塔区17569777706： 计算机数据结构:尾插法怎么实现单链表的逆置? - ？
督芬赐尔： 假设已有一个单链表,头结点是struct node *first;结点若干,可用尾插法反转单链表,C语言代码如下: void Reverse_List (struct node *first) {struct node *rear,*temp,*p; for(rear = first ; rear->next != NULL ; rear->next = rear->next->next);p = ...

宝塔区17569777706： 【数据结构题】设计一个算法,要求用栈结构将带头结点的单链表逆置.写出完整的程 - ？
督芬赐尔： #include <stdio.h> #include <stdlib.h> #include <time.h>typedef struct Node {int data;struct Node * next; }Node, * LinkList;void ListReverse(LinkList L) {Node *p,*q;p=L->next;L->next=NULL;while(p){q=p->next;p->next=L->next;//头插法L-...

宝塔区17569777706： 设计一个算法将带头结点的单链表逆置? - ？
督芬赐尔： 链表反序,设有数据结构 typedef struct _list_node { double keyVal; struct _list_node *next; }ListNode; ListNode* reverseList(ListNode* head) { ListNode *p1, *p2 , *p3; //链表为空,或是单结点链表直接返回头结点 if (head == NULL || head->next ==...

宝塔区17569777706： 求数据结构中C语言版 带头结点的单链表的置逆算法 - ？
督芬赐尔： #include<stdio.h> #include<malloc.h> struct node {int n;struct node *next; }main() {struct node *head,*p,*q,*r;int n,m,i=0;head=(struct node*)malloc(sizeof(struct node));//申请头结点q=(struct node*)malloc(sizeof(struct node));//申请最后一...

宝塔区17569777706： 求两个单链表逆置的算法. - ？
督芬赐尔： 请按照自己的类型和成员来修改其中的东西:void Reverse_L1(LNode * &head) {// 有表头结点链表,从第一结点开始颠倒 LNode *p = head->next;// p 指向第一个结点 head->next = NULL;// 断开链表表头 while (p != NULL) { LNode *q = p; p = p->...

宝塔区17569777706： 两题单链表逆置,求讲解 - ？
督芬赐尔： 第一个,有头结点的单链表,从头到尾顺次摘下所有结点并插入在表头: p=head->next; p指向第一个结点head->next=NULL; 断开头结点和链表while(p)当链表不为空时{s=p;中间指针保存当前结点好摘下p=p->next;当前指针后移s->next...

宝塔区17569777706： 将带头结点的单链表利用原表空间逆置: - ？
督芬赐尔： 用另一节点保存第一个值,将要交换的第一个值付给第一个节点,依次下去.直到还完.时间复杂度n,空间复杂度1

宝塔区17569777706： 用c语言实现单链表的逆置,能将此程序详细的解释一下吗? - ？
督芬赐尔： 用c语言实现单链表的逆置的方法:p=head; s=p->next; while(s->next!=NULL) t=s->next; s->next=p; s=t; s->next=p; head->next->next=NULL; head->next=s; p=head; //p最开始指向头结点 s=p->next; //s最开始指向第一个节点 while(s->next!=NULL)//...