现在的位置: 首页 > 综合 > 正文

基于visual Studio2013解决面试题之0604O(1)时间复杂度删除链表节点

2013年02月24日 ⁄ 综合 ⁄ 共 1401字 ⁄ 字号 评论关闭


题目

解决代码及点评

/*
	在O(1)时间内删除链表节点

	链表结构体
	class ListNode
	{
	public:
		ListNode* _next;
		int _data;
	};

	class List
	{
	public:
		ListNode* _head;

		void rm(ListNode* node)
		{
			// TODO: remove the node in O(1)
		}
	};

	一般情况下,链表删除,需要遍历到被删除节点的上一个节点,然后做删除,
	时间复杂度是O(n),如何在链表节点已知情况下,O(1)时间内做删除呢

	思路:将该链表节点的数据,和它的next节点数据互换,这样当前节点就成了prev节点了
	      要删除的是它的下一个,这样就不用去寻找了
		  特例:当该节点在最尾部时,还是需要去寻找
	那么在n个节点的链表里,有n-1个链表节点是O(1)复杂度,只有一个节点是O(N)复杂度
	平均还是O(1)复杂度

*/
#include <iostream>
using namespace std;

class ListNode
{
public:
	ListNode* _next;
	int _data;
	ListNode(int data, ListNode* next=NULL) :_data(data), _next(next){}
};

class List
{
public:
	ListNode* _head;
	List(ListNode* head = NULL) :_head(head){}

	void add(int data)
	{
		_head = new ListNode(data, _head);
	}

	// O(1)时间内删除节点
	void rm(ListNode* node)
	{
		if (node->_next)  // 如果该节点的next不为空
		{
			ListNode* next = node->_next; 
			node->_data = next->_data;  // 将next节点的data拷贝到要被删除的节点上
			node->_next = next->_next;  //  真正删除的是该节点的下一个节点
			delete next;
		}
		else  // 如果该节点的next为空
		{
			ListNode* prev;  
			for (prev = _head; prev->_next != node; prev = prev->_next);  // 遍历定位prev指针  
			prev->_next = NULL;  // 让prev的next为空
			delete node;
		}
	}

	void print()
	{
		for (ListNode* node = _head; node; node = node->_next)
		{
			cout << node->_data << " ";
		}
		cout << endl;
	}
};

// 测试主函数
int main()
{
	List l;
	// 构造链表
	for (int i = 0; i < 10; i++)
	{
		l.add(i);
	}

	// 打印
	l.print();
	
	// 随意删除一个节点
	ListNode* node = l._head->_next->_next;
	l.rm(node);

	// 在打印
	l.print();
	system("pause");
}

代码下载及其运行

代码下载地址:http://download.csdn.net/detail/yincheng01/6704519

解压密码:c.itcast.cn

下载代码并解压后,用VC2013打开interview.sln,并设置对应的启动项目后,点击运行即可,具体步骤如下:

1)设置启动项目:右键点击解决方案,在弹出菜单中选择“设置启动项目”

【上篇】
【下篇】

抱歉!评论已关闭.