文章目录如果您是第一次看我写的博客,可以给我点个赞并关注我吗,我会持续分享更多有意思的干货。
1 题目2 思路3 代码4 小结 1 题目
剑指 Offer 24、反转链表
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
2 思路示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL限制:
0 <= 节点个数 <= 5000
最开始我是想尝试用头插法的思路,把数据从原有的链表中读取出来后用头插法放入一个新链表中。但是我犯了一个错误,原题意没有头结点!所以头插法在没有头结点的情况下就显得有点无奈了。
为此在网上翻阅步骤后,我学到了一个小窍门,即无需创建一个新的链表,在原有链表的基础上,我们可以改动原来链表指针的朝向即可。
既然有了思路,我们立马动手吧!
3 代码class Solution {public: ListNode* reverseList(ListNode* head) { ListNode * cur = head; ListNode * pre = NULL; ListNode * Temp = NULL; while(cur != NULL) { Temp = cur->next; cur->next = pre; pre = cur; cur = Temp; } return pre; }};
4 小结实际上,如果在最后的题意中能够把head指向逆置链表的首元节点就更完美了。对于这道题的解法来说时间复杂度是O(n),空间复杂度是O(1),其花的时间主要用于遍历上。