您现在的位置是:首页 >技术交流 >单链表OJ题:LeetCode--206.反转链表网站首页技术交流
单链表OJ题:LeetCode--206.反转链表
简介单链表OJ题:LeetCode--206.反转链表
朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode中206题:反转链表
数 据 结 构:数据结构专栏
作 者:stackY、
C 语 言 :C语言专栏
LeetCode :LeetCode刷题训练营
LeetCode--206.反转链表: https://leetcode.cn/problems/reverse-linked-list/description/
目录
1.题目介绍
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
2.实例演示
3.题解思路
反转链表有两种思路:
1.直接改变链表的指向。
2.使用结点直接进行头插。
3.1改变结点的指向
如果链表为空直接返回NULL,若不为空,先记录头结点(n2)和头结点的下一个位置(n3),然后设置一个指针(n1),先置为NULL,然后将头指针(n2)指向n1,这时头指针就需要向后面后一步,因此需要将n3赋给n2,n2赋给n1,再将n3向后走一步,再让新的头指针(n2)指向新的n1,再往后面走,依次类推,直到遍历完整个链表,这里要注意,如果n3已经为空,那么n3就不能走了,如果n2为空,链表就反转结束。这时n1就变成了新的头,返回n1就可以了。
代码演示:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ //链表为空直接返回 if(head == NULL) { return NULL; } struct ListNode* n1 = NULL; struct ListNode* n2 = head; struct ListNode* n3 = head->next; //遍历 while(n2) { //改变头结点的指向 n2->next = n1; //更新新的结点 n1 = n2; n2 = n3; //n3不为空才可以指向下一个 if(n3 != NULL) n3 = n3->next; } //返回新的头 return n1; }
3.2头插法
取结点进行新一轮的头插就比较简单,只需要记录头结点的下一个结点的位置,然后头插,迭代,这里也不需要考虑第一次插入是空指针的问题,直接插入,然后返回新的头。
代码演示:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead = NULL; struct ListNode* cur = head; while(cur) { //保存头结点的下一个结点 struct ListNode* next = cur->next; //头插 cur->next = newhead; //更新新的头 newhead = cur; //迭代 cur = next; } return newhead; }
今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!!
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。