编程之美--3.4

题目描述：删除没有头结点的链表的指定节点

思路：这道题和面试金典那道题有点像，当时的思路是将后面节点赋值到当前节点，最后删除尾节点，但是那样的话就会出现（1）尾节点没法删除（2）时间复杂度为O（n）；

这里换个思路，删除当前节点的下一个节点，把下个节点的值赋给当前节点，复杂度为O（1）。尾节点单独处理。

未测试版代码如下：

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 using namespace std;
 8 
 9 struct node
10 {
11     node *next;
12     int val;
13     node(int p):val(p),next(NULL){}
14 };
15 
16 void fun(node *pCur)
17 {
18     node *pNext = pCur->next;
19     if(pNext != NULL)
20     {
21         pCur->val = pNext->val;
22         pCur->next = pNext->next;
23         delete pNext;
24     }
25 }
26 
27 int main()
28 {
29     return 0;
30 }

扩展问题：给定链表头指针，只遍历一次，将链表反转？这个很简单，每次将当前结点插入到头指针后面即可。代码就不写了。