前言:
🎈欢迎大家来到Dream_Chaser~的博客🎈
🚩本文收录于 C--数据结构刷题的专栏中 -->http://t.csdn.cn/n6UEP
首先欢迎大家的来访,其次如有错误,非常欢迎大家的指正,互相学习进步。
一.反转链表
来源:206. 反转链表 - 力扣(LeetCode)
题目:
1.迭代法
思路:
- 首先,检查链表头节点是否为空。如果为空,表示链表为空,直接返回NULL。
- 定义三个指针变量:n1、n2和n3。初始时,n1指向NULL,n2指向头节点head,n3指向n2的下一个节点。
- 进入循环,条件是n2不为NULL。循环的目的是将当前节点n2的指针指向它的前一个节点n1,实现反转。
- 在循环内部,首先将n2的next指针指向n1,完成反转操作。
- 然后,更新n1、n2和n3的值。将n2赋值给n1,将n3赋值给n2,同时判断n3是否为NULL,如果不为NULL,则将n3更新为n3的下一个节点。
- 当循环结束时,所有节点都被反转了,n1指向原链表的最后一个节点,也就是反转后的链表的头节点。
- 返回n1,作为反转后的链表的头节点。
动图演示:
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) return NULL; struct ListNode* n1 = NULL; struct ListNode* n2 = head; struct ListNode* n3 = n2->next; while (n2) { n2->next = n1; n1 = n2; n2 = n3; if (n3)//加上这里的原因,当n2指向最后一个结点时.此时n3已经为NULL n3 = n3->next;//若对空指针解引用就会出现异常 } return n1; }
代码执行:
注意:如果去掉条件if(n3)则会出现问题
原因:
if (n3) 加上此条件的原因,当n2指向最后一个结点时.此时n3已经为NULL
n3 = n3->next;//若对空指针解引用就会出现异常
执行:
2.头插法
- 创建两个指针变量:cur和rhead。cur用于迭代遍历原始链表,rhead用于指向反转后的链表的头部。
- 进入while循环,循环条件为cur不为NULL,即还未遍历完原始链表。
- 在循环内部,首先创建一个指针变量next,用于保存cur的下一个节点的地址,以防止丢失。
- 执行头插操作,将cur节点插入到反转链表的头部。将cur的next指针指向rhead,实现插入操作。然后更新rhead,使其指向cur,将cur成为新的头部。
- 更新cur,使其指向next,继续迭代遍历原始链表的下一个节点。
- 循环结束后,原始链表遍历完毕,整个链表已经完成反转。返回rhead,即为反转后的链表的头部
动图演示:
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head,*rhead=NULL; while(cur) { struct ListNode* next=cur->next; //头插 cur->next=rhead; rhead=cur; //迭代 cur=next; } return rhead; }
执行:
本文到此结束,如有错误,欢迎大家指正,感谢来访。🚩