想问为什么不能使用单链表

原题链接：https://www.nowcoder.com/share/jump/8007959361687254085116

这是一道链表模板题，算法时间复杂度体现在寻找链表元素上，数据量为n = 10^4,时间复杂度为O(n^2).想问有没有人可以解释一下，使用双链表就不会超时，而使用单链表就会超时呢？时间复杂度不都是一样的吗？

按理说不应该会，是不是你的代码有什么问题。单链表复杂度应该一样。

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7648334
• 这篇博客你也可以参考下：【算法题】输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为o(n)。
• 除此之外, 这篇博客: 【数据结构】-单链表(带头结点）中的 4.4.2.1 删除法1(时间复杂度为O(n)) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• //4-2-1.指定结点的删除：删除指定的元素p---法1：老实人O(n)
  bool DeleteNode1(LinkList& L, LNode* p) {
  	if (p == NULL)
  		return false;
  	LNode* q;		//设q为p的前驱结点
  	q = L;
  	while (q != NULL && q->next != p)	//遍历找到p的前驱结点q
  		q = q->next;		
  	if (q == NULL)
  		return false;
  	q->next = p->next;
  	free(p);
  	return true;
  }