【校招面试 之 剑指offer】第18题 删除链表中的节点

题目一:在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;
}
原文地址:https://www.cnblogs.com/xuelisheng/p/9369953.html