左神算法基础class3—题目7反转单向和双向链表

本文主要是介绍左神算法基础class3—题目7反转单向和双向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

左神算法基础class3—题目7反转单向和双向链表

题目1：反转单向链表
- 1.分析
- 2.核心代码
- 3.完整代码
- 4.输出结果
题目2：反转双向链表
- 1.分析
- 2.核心代码
- 3.完整代码
- 4.输出结果

题目1：反转单向链表

【要求】如果链表长度为N，时间复杂度要求为O(N)，额外空间
复杂度要求为O(1)

1.分析

反转单向链表可以使用迭代法，需要三个指针分别记录前一个节点，当前节点和后一个结点。反转时把当前节点指向前一个节点，再把当前节点和前一个节点都后移，继续反转直到末尾。因为反转过后当前节点指向发生变化与之后的节点会断开，所以需要指针来保存当前节点的后一个节点。整体迭代的条件是当前节点不为空。

2.核心代码

（1）生成完整的链表
①数据结构如下，val为数据域，*next指向下一节点，由于指向的是节点，所以需要定义为ListNode型指针。

typedef struct ListNode
{int val;ListNode *next;
}*List;

②使用尾插法：将新加入的节点插入末尾

malloc负责开辟一块空间存储，空间大小是sizeof(ListNode),由于malloc默认返回void*，需要强制转换为List型结构体指针。L为头节点不用于存储数据，只用于存放链表头的地址，将尾节点暂时指向头节点。开辟p节点存储数据，将尾节点指向新的节点构成链表再把新的节点设置为尾节点，继续开辟新结点再存储。最后把尾节点指向空。

	ListNode* L = (List)malloc(sizeof(ListNode));//List L = (List)malloc(sizeof(ListNode));与上式等价L->next = NULL;//使用尾插法List p,r;//p是新结点，r是尾节点r = L;	//把尾节点指向头节点for(int i = 0;i < N;i++){p = (List)malloc(sizeof(ListNode));p->val = i * 5;r->next = p;r = p;}r->next = NULL;

(2)反转单链表

List reverseList(List head) 
{List pre = NULL;List cur = head->next;//需要反转的当前节点从头节点的下一个开始while(cur != NULL){List temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;
}

3.完整代码

#include<iostream>
#include<stdlib.h>
//#include<time.h>
#define N 5
typedef struct ListNode
{int val;ListNode *next;
}*List;List reverseList(List head) 
{List pre = NULL;List cur = head->next;while(cur != NULL){List temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;
}int main()
{//srand(time(0));ListNode* L = (List)malloc(sizeof(ListNode));//List L = (List)malloc(sizeof(ListNode));与上式等价L->next = NULL;//使用尾插法List p,r;//p是新结点，r是尾节点r = L;	//把尾节点指向头节点for(int i = 0;i < N;i++){p = (List)malloc(sizeof(ListNode));//p->val = rand() % 15;p->val = i * 5;r->next = p;r = p;}r->next = NULL;List newhead = NULL;newhead = reverseList(L) ;system("pause");return 0;
}

4.输出结果

L是原来的单向链表，第一个val是头节点；
在这里插入图片描述
反转后的单向链表。

题目2：反转双向链表

反转单向和双向链表
【题目】分别实现反转单向链表和反转双向链表的函数。
【要求】如果链表长度为N，时间复杂度要求为O(N)，额外空间
复杂度要求为O(1)

1.分析

双向链表的反转只需要把当前节点的next指针和pre指针交换即可，对每个节点单独操作，不涉及其他节点。

2.核心代码

（1）双向链表的创建
双向链表的数据结构由一个数据域两个指针域构成；


typedef struct doublelist
{int val;doublelist* next;doublelist* pre;}*List;

双向链表的尾插法和单向链表基本相同,只是增加了记录pre指针的步骤；

	List p,r,head = NULL;r = NULL;for(int i = 0;i < 4;i++){p = (List)malloc(sizeof(doublelist));p->val = 5 * i;p->pre = r;if(r == NULL){r = p;head = p;continue;}r->next = p;r = p;}r->next =NULL;

（2）反转双向链表
使用中间变量暂存next指针，再交换next和pre指针，最后把前一个指针指向的结点赋给当前节点，继续进行反转。注意，因为next指针已经和pre指针交换了，所以前一个指针指向的节点实际就是下一个节点。

List reverseList(List head) 
{List p = head;List temp = NULL;while(p!=NULL){temp = p->next;p->next = p->pre;p->pre = temp;p = p->pre;}return head;
}

3.完整代码

#include<iostream>typedef struct doublelist
{int val;doublelist* next;doublelist* pre;}*List;List reverseList(List head) 
{List p = head;List temp = NULL;while(p!=NULL){temp = p->next;p->next = p->pre;p->pre = temp;p = p->pre;}return head;
}int main()
{List p,r,head = NULL;r = NULL;for(int i = 0;i < 4;i++){p = (List)malloc(sizeof(doublelist));p->val = 5 * i;p->pre = r;if(r == NULL){r = p;head = p;continue;}r->next = p;r = p;}r->next =NULL;List newhead = NULL;newhead = reverseList(head) ;return 0;
}