(算法总结)单链表的就地逆置(leetcode 206)
程序员文章站
2022-06-06 13:36:27
...
单链表是大家非常熟悉的数据结构,单链表的就地逆置是面试算法中常考的问题。“就地”逆置就是要求算法不引入额外的存储空间,即算法的空间复杂度为O(1),换句话讲,算法要求我们只使用指针的移动和变换,来实现逆置的功能。我们这里使用一种典型的方法“头插法”。
先定义一个单链表的数据节点:
struct ListNode
{
int val;
ListNode *next;
ListNode(int x): val(x), next(NULL) {}
};
头插法来逆置单链表,其实是四步操作,分别对应于下图中的(1)——(4):
这里使用临时头结点来简化算法
代码实现如下:
ListNode* inverse_list(ListNode* head) {
ListNode tempNode(-1); // 临时头结点
ListNode* ptr = &tempNode;
while (head) {
ListNode* next = head->next;
head->next = ptr->next;
ptr->next = head;
head = next;
}
return tempNode.next;
}
下一篇: python学习第一天