关于单链表安插算法时间复杂度的疑惑

关于单链表插入算法时间复杂度的疑惑
在长度为n的单链表L的第i位置插入元素e：
（1）找出第（i-1）个结点，记为*p,然后将新结点插到p的后面，其时间复杂度为O(n).
（2）直接在第i个结点的后面插入新结点，然后将两个结点的数据交换一下，以达到目的。此时时间复杂度为O(1).
王道的考研书上这样写的。
我不明白（2）中的时间复杂度为什么是O(1)，直接在i后面插入新结点是不需要找第（i-1）个结点了，可找第i个结点结果不是一样吗？
希望有大神帮我解释一下！！！
------解决方案--------------------
他的意思估计是在第i位置的指针*q已知的情况下，要在q之前插入一个元素的复杂度。
------解决方案--------------------
第i个节点的指针已知了。有些人自建的链表会返回第m个节点的指针的


------解决方案--------------------

void insert(int i, int item) {  //在第i（i=1,2,3...）个结点处插入值为item的元素

	Node* p=head;  //p指向当前第j个结点，初始指向第0个结点即头结点

	int j=0;  

	while(p && j<i-1) {  //此循环的目的是让p指向第i-1个结点

		p=p->next;

		j++;

	}

	if(!p) {

		cerr << "插入位置非法！"; exit(1);

	}

	else {

		Node* s=new Node;  //new新结点，s指向之

		s->data=item;  

		s->next=p->next;  //新结点指向原来的第i个（插入后是第i+1个了）元素

		p->next=s;  //原来的第i-1个结点指向新结点

	}

} 

时间复杂度为O(n)的while循环后得到的指针p指向第i-1个结点，那p->next指向的就是第i个结点了~已经执行过while循环找到了p，那么后面新建结点的操作只需要执行一次，因此时间复杂度是O(1)。LZ可以试试画图
------解决方案--------------------

引用:

嗯 好像也只有这样说的通了，不过，算法中说的是在第i处插入新结点，还是不怎么理解

还是要谢谢两位

你原来的*q是第i个位置，你要插入到第i个位置，那么插入以后新元素是第i个位置，q变成第i+1个位置。
------解决方案--------------------
插入是insert...invert是逆置

在长度为n的单链表L的第i位置插入元素e：
后插法：找到第i-1个位置，在它后面插入元素e
1.找到第i-1个结点，O(n)
2.new结点，放在第i-1个结点后面，O(1)
总执行次数n+1，时间复杂度是O(n)

前插法：找到第i个位置，在它前面插入元素e
1.找到第i个结点，O(n)
2.找到第i-1个结点，O(n),单链表一般是前面元素指向后面元素，找到第i个结点不能直接指向第i-1个结点，需要从head重新再找一次；所谓“前面后面”也是由元素之间的指向关系决定的，如果允许，三叉链表可以直接指向“前面”和“后面”，牺牲空间换取时间
3.new结点，放在第i-1个结点后面，O(1)
总的执行次数是2n+1，时间复杂度也是O(n)，时间复杂度的计算是数量级的，只看最高次而且忽略系数
前插法比后插法多了第1步

插入操作执行完当然要销毁本地变量p，链表已经插入新结点了，下一次执行这个新结点跟普通的结点毫无差别；下一次插入（遍历/查找/删除）有它独立的while，保存上一次操作的指针p没什么用，而且p作为变量是要占空间的，即使有用也还是以空间换时间。加入数据特别大，到了要保存指针节省时间这种骇人听闻的程度，也许可以考虑链表以外的其他数据结构了
------解决方案--------------------
比如链表和数组都知道要插入位置的情况下，链表是直接插入，而数组要各个元素向后移腾出位置~~~这就是为什么一个是0（1），一个是0（n）我也买王道了