数据结构 求将单链表逆置的的时间复杂度 详细解释 高手来
作者&投稿:定育 (若有异议请与网页底部的电邮联系)
算法利用的是链表的头插入法,结果是与插入次序正好颠倒
//这是有表头结点链表的逆置
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)
督芬赐尔: 算法利用的是链表的头插入法,结果是与插入次序正好颠倒 //这是有表头结点链表的逆置 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)//...