欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(算法总结)单链表的就地逆置(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):

(算法总结)单链表的就地逆置(leetcode 206)

这里使用临时头结点来简化算法

代码实现如下:

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;
}
相关标签: 单链表