题目描述
- 给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间内删除该节点
- 链表节点与函数的定义如下
struct ListNode{
int value;
ListNode *next;
}
题目解读
- 剑指Offer 119
- 把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除
代码
第二轮代码是在第一轮代码基础上集合书上代码修改的
- 第二轮代码
#include<iostream>
using namespace std;
struct ListNode{
int value;
ListNode *next;
};
// Print
void PrintList(ListNode *head){
if(!head){
cout<<"链表为空"<<endl;
}
else{
while(head){
cout<<head->value<<" ";
head = head->next;
}
cout<<endl;
}
}
ListNode* DeleteNode(ListNode *head, ListNode *toBeDelete){
// 分三种情况
// 1、欲删除节点是首节点
// 2、欲删除节点是中间节点(非首尾节点)
// 3、欲删除节点是尾节点
// 增强代码鲁棒性
if(! head || ! toBeDelete){
cout<<"输入有误，请重新输入"<<endl;
}
else{
if(toBeDelete->next){ // 1、欲删除节点是中间节点(非首尾节点)
ListNode *temp;
temp = toBeDelete -> next;
toBeDelete->value = temp->value;
toBeDelete->next = temp->next;
delete temp;
}
else if(toBeDelete == head){ // 2、欲删除节点是首节点
delete toBeDelete;
toBeDelete = NULL;
head = NULL;
}
else{ // 3、欲删除节点是尾节点,此处需要判断一下尾节点是否是toBeDelete
ListNode *pre;
ListNode *current;
pre = head;
current = pre->next;
while(current->next){
pre = current;
current = pre->next;
}
if(current == toBeDelete){
pre->next = NULL;
delete current;
}
}
}
return head;
}
// Create
ListNode* createList(){
// 运行正确
// int node[10] = {1, 2, 3, 3, 4, 4, 5};
// int length = 7;
// 验证只有一个节点的情况，通过
int node[10] = {1};
int length = 1;
ListNode *head = NULL;
ListNode *tail = NULL;
for(int i=0; i < length; i++){
ListNode *p = new ListNode();
p -> value = node[i];
p -> next = NULL;
if(!head){
head = p;
tail = head;
}
else{
tail -> next = p;
tail = p;
}
}
// PrintList(head);
return head;
}
int main(){
ListNode *head;
ListNode *toBeDelete;
head = createList();
// PrintList(head); // 验证链表是否成功建立
int todelete = 1; // 此处设置删除的位置
for(int i=0; i < todelete; i++){
if(i == 0){
toBeDelete = head;
}
else{
toBeDelete = toBeDelete->next;
}
}
head = DeleteNode(head, toBeDelete);
PrintList(head);
}
- 第一轮代码
#include<iostream>
using namespace std;
struct ListNode{
int value;
ListNode *next;
};
// Print
void PrintList(ListNode *head){
if(!head){
cout<<"链表为空"<<endl;
}
else{
while(head){
cout<<head->value<<" ";
head = head->next;
}
cout<<endl;
}
}
ListNode* DeleteNode(ListNode *head, ListNode *toBeDelete){
// 分三种情况
// 1、欲删除节点是首节点
// 2、欲删除节点是中间节点(非首尾节点)
// 3、欲删除节点是尾节点
// 增强代码鲁棒性
if(! head || ! toBeDelete){
cout<<"输入有误，请重新输入"<<endl;
}
else{
// 1、欲删除节点是首节点
if(head == toBeDelete){
// 又分两种情况，链表是否只有一个节点
// 链表只有一个节点
if(! head->next){ // 此处有点小问题，第二轮再修改！ 即当我这个函数无返回值时，此处无效
head = NULL;
PrintList(head);
}
else{ //链表有多个节点
ListNode *temp;
temp = toBeDelete -> next;
toBeDelete->value = temp->value;
toBeDelete->next = temp->next;
delete temp;
}
}
else if(toBeDelete->next){ // 2、欲删除节点是中间节点(非首尾节点)
ListNode *temp;
temp = toBeDelete -> next;
toBeDelete->value = temp->value;
toBeDelete->next = temp->next;
delete temp;
}
else{ // 3、欲删除节点是尾节点,此处需要判断一下尾节点是否是toBeDelete
ListNode *pre;
ListNode *current;
pre = head;
current = pre->next;
while(current->next){
pre = current;
current = pre->next;
}
if(current == toBeDelete){
pre->next = NULL;
delete current;
}
}
}
return head;
}
// Create
ListNode* createList(){
// 运行正确
// int node[10] = {1, 2, 3, 3, 4, 4, 5};
// int length = 7;
// 验证只有一个节点的情况，通过
int node[10] = {1};
int length = 1;
ListNode *head = NULL;
ListNode *tail = NULL;
for(int i=0; i < length; i++){
ListNode *p = new ListNode();
p -> value = node[i];
p -> next = NULL;
if(!head){
head = p;
tail = head;
}
else{
tail -> next = p;
tail = p;
}
}
// PrintList(head);
return head;
}
int main(){
ListNode *head;
ListNode *toBeDelete;
head = createList();
// PrintList(head); // 验证链表是否成功建立
int todelete = 1; // 此处设置删除的位置
for(int i=0; i < todelete; i++){
if(i == 0){
toBeDelete = head;
}
else{
toBeDelete = toBeDelete->next;
}
}
head = DeleteNode(head, toBeDelete);
PrintList(head);
}
总结展望
- 熟悉链表删除操作..
