题目一：在O(1)时间内删除链表节点。
给定单项链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
思路：（1）如果要删除的节点不是链表的尾节点，则将被删除节点的内容复制到该节点，然后删除被复制的节点。
（2）如果删除的节点为链表节点的尾节点，则我们需要从头结点开始遍历到尾节点的前驱节点，删除尾节点。
（3）如果链表只有一个节点（除了头结点），则按着（2）删除的同时，还需要head->next = NULL；
#include<iostream>
using namespace std; template<typename T>
struct listNode{
T data;
listNode *next;
}; template<typename T>
listNode<T> *create(listNode<T> *list){
listNode<T> *head = list; // 头结点
T tempData;
cout<<"输入元素(int)，以空格分开，输入-1结束："<<endl;
while(1){
cin>>tempData;
if(tempData == -1){
return head;
}else{
listNode<T> *p = new listNode<T>();
p->data = tempData;
p->next = head->next;
head->next = p;
}
}
return head;
} template<typename T>
void outputList(listNode<T> *list){
listNode<T> *tempList = list->next;
while(tempList){
cout<<tempList->data<<" ";
tempList = tempList->next;
}
cout<<endl;
} template<typename T>
listNode<T> *searchListNode(listNode<T> *list, T t){
listNode<T> *tempList = list->next;
while(tempList){
if(tempList->data == t){
return tempList;
}else{
tempList = tempList->next;
}
}
cout<<"查找节点不存在！"<<endl;
} template<typename T>
void deleteListNode(listNode<T> *list, listNode<T> *deleteListNode){
listNode<T> *tempListNode = list;
// 首先判断是否是尾节点
if(deleteListNode->next == NULL){
if(tempListNode->next == deleteListNode){
delete deleteListNode;
tempListNode->next = NULL;
return;
}else{
// 常规的删除尾节点的方式（从头遍历到尾节点的前驱节点）
while(tempListNode->next != deleteListNode){
tempListNode = tempListNode->next;
}
delete deleteListNode;
tempListNode->next = NULL;
return;
}
}
// 使用纯的O(1)时间删除节点
listNode<T> *tempListNode1 = deleteListNode->next;
deleteListNode->data = tempListNode1->data;
deleteListNode->next = tempListNode1->next;
delete tempListNode1;
}
/*
测试用例1：1 2 3 4 5 6 7 -1
测试用例2：1 2 4 5 6 7 3 -1
测试用例3：3 1 2 4 5 6 7 -1
测试用例4：3 -1
*/
int main(){
listNode<int> *list = new listNode<int>();
listNode<int> *searchReturnlistNode = NULL;
// create list
create(list);
// output list
outputList(list);
// search and return which listNode value is 3
searchReturnlistNode = searchListNode(list, 3);
// cout<<"验证一下（whether equals 3）："<<searchReturnlistNode->data<<endl;
// delete listNode
deleteListNode(list, searchReturnlistNode);
// check in list when delete listNode
outputList(list);
system("pause");
return 0;
}
题目2：删除链表中重复的节点。
在一个排序的链表中，如何删除重复的节点？
思路：常规思路
#include<iostream>
using namespace std; template<typename T>
struct listNode{
T data;
listNode *next;
}; template<typename T>
listNode<T> *create(listNode<T> *list){
listNode<T> *head = list; // 头结点
T tempData;
cout<<"输入元素(int)，以空格分开，输入-1结束："<<endl;
while(1){
cin>>tempData;
if(tempData == -1){
return head;
}else{
listNode<T> *p = new listNode<T>();
p->data = tempData;
p->next = head->next;
head->next = p;
}
}
return head;
} template<typename T>
void outputList(listNode<T> *list){
listNode<T> *tempList = list->next;
while(tempList){
cout<<tempList->data<<" ";
tempList = tempList->next;
}
cout<<endl;
} //
template<typename T>
void deleteRepeatListNodeValue(listNode<T> *list){
listNode<T> *tempListNode = list->next;
while(tempListNode->next){
if(tempListNode->data == tempListNode->next->data){
listNode<T> *tempListNode1 = tempListNode->next;
tempListNode->next = tempListNode1->next;
delete tempListNode1;
}else{
tempListNode = tempListNode->next;
}
}
} int main(){
listNode<int> *list = new listNode<int>();
listNode<int> *searchReturnlistNode = NULL;
// create list
create(list);
// output list
outputList(list); //delete repeat values
deleteRepeatListNodeValue(list);
// check in list when delete repeat values in listNode
outputList(list);
system("pause");
return 0;
}