首页 > 代码库 > 数据结构与算法分析 3.12 — 单链表转置
数据结构与算法分析 3.12 — 单链表转置
题目一: 不含头结点的单链表转置，算法时间复杂度O(N)
代码如下：
struct LNode;typedef struct LNode *List;typedef struct LNode *Position;struct LNode{ ElementType elem; Position next;};/* 无头结点单链表转置 */List Reversion(List L){ Position previousPos, currentPos, nextPos; previousPos = nullptr; currentPos = L; nextPos = L->next; while (nextPos != nullptr) { currentPos->next = previousPos; previousPos = currentPos; currentPos = nextPos; nextPos = nextPos->next; } currentPos->next = previousPos; return currentPos;}
题目二: 带头结点的单链表转置，算法时间复杂度O(N)
struct LNode;typedef struct LNode *List;typedef struct LNode *Position;struct LNode{ ElementType elem; Position next;};/* 带头结点单链表转置 */List Reversion(List list){ List header = list; List currentPos = header->next; header->next = nullptr; while (currentPos != nullptr) { Position tmp = currentPos; currentPos = currentPos->next; tmp->next = header->next; header->next = tmp; } return header;}
数据结构与算法分析 3.12 — 单链表转置
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。