代码:
//带有头指针的链表操作
//2014.7.6
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node
{
int data;
struct node *next;
}Node;
void insert_node(Node **pphead,int v)
{
if(*pphead==NULL)
{
*pphead=(Node *)malloc(sizeof(Node));
(*pphead)->data=v;
(*pphead)->next=NULL;
}
else
{
Node *t=*pphead;
*pphead=(Node *)malloc(sizeof(Node));
(*pphead)->data=v;
(*pphead)->next=t;
}
}
//--------------------------------------------------------------------------------------------------------平均时间复杂度为O(1)的节点删除算法
void delete_node1(Node **pphead,int v)//参考剑指offer ,面试题13,酷壳linus
{
Node *pNode=*pphead;
while(pNode!=NULL)
{
if(pNode->data==v)
break;
else
pNode=pNode->next;
}
if(pNode==NULL)//遍历整个链表,没有找到对应节点
{
cout<<"No node with v value exist"<<endl;
}
//要找的节点是尾节点(或者当链表中只有一个节点,且该节点就是要找的那个节点时)时,
//由于无法再用“将要删除节点A的后继节点B的内容赋值给A,并将A的next指针指向B的后继节点,然后free(B)”,
//只能用顺序查找的方法找到A的前驱节点C,让C指向A的后继节点
else if(pNode->next==NULL)
{
Node *pre=*pphead;
while(pre->next!=pNode)
{
pre=pre->next;
}
pre->next=NULL;
free(pNode);
pNode=NULL;
}
//当链表中的节点不是尾结点时,“将要删除节点A的后继节点B的内容赋值给A,并将A的next指针指向B的后继节点,然后free(B)”
else
{
Node *pNext=pNode->next;
pNode->next=pNext->next;
pNode->data=pNext->data;
free(pNext);
pNext=NULL;
}
}
//---------------------------------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------------------时间复杂度为O(n),比较经典的的一种方法
void delete_node2(Node **pphead,int v)
{
Node *cur=*pphead;
Node *pre=NULL;
if(cur==NULL)
{
cout<<"Now ,the link is empty!"<<endl;
return;
}
for( ;cur;pre=cur,cur=cur->next)
{
if(cur->data==v)
break;
}
if(pre==NULL)//要删除的是第一个节点
{
//Node *pnode=*pphead;
*pphead=cur->next;
free(cur);
}
else
{
pre->next=cur->next;
free(cur);
}
}
//---------------------------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------利用二级指针进行链表节点的删除,时间复杂度为O(1)
//---*********************************该方法是效率最高的一种删除链表节点的方法,利用二级指针进行链表的**************************************
void delete_node3(Node **pphead,int v)
{
Node **cur=pphead;
for(cur=pphead;*cur;)
{
Node *en=*cur;
if(en->data==v)
{
*cur=en->next;
free(en);
break;
}
else
{
cur=&en->next;
}
}
}
void print_node(Node **pphead)
{
for(Node *cur=*pphead;cur;cur=cur->next)
cout<<cur->data<<" ";
cout<<endl;
}
int main(void)
{
Node *firNode=NULL;
for(int i=1;i<=10;i++)
insert_node(&firNode,i);
print_node(&firNode);
delete_node1(&firNode,10);
delete_node2(&firNode,1);
delete_node3(&firNode,3);
delete_node3(&firNode,9);
print_node(&firNode);
}
分享到:
相关推荐
面试题13:机器人的运动范围 +2 DFS+BFS 面试题14 - I:剪绳子 +2 动态规划 面试题14 - II:剪绳子 +2 动态规划 面试题15:二进制中1的个数 +2 规律题位运算 面试题16:数值的整数次方 +2 递归+迭代 面试题17:打印...
面试题_数字表示剑指offer第二版的题号,四位数字表示leetcode题库的题号,其他的在文件夹其他常见算法题中。 其中《剑指Offer》书中相关试题的Python实现主要参考《剑指offer(第二版)》和。 哈希表: 面试题50:...
题目描述 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 原创文章 264获赞 692访问量 3万+ 关注 私信 展开阅读全文 作者:程旭员
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
【面试题06】从尾到头打印链表 难度: 简单 限制: 0 <= 链表长度 <= 10000 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 Leetcode题目对应位置: 面试题06:从尾到头打印链表 思路...
1、剑指解析: 2、特殊用例: 3、代码实现: I、原地双指针(从后向前复制) 从后向前复制是《剑指》推荐的一种解法,可以适用于各种编程语言。每' '比' '多两个字符。两个指针都是从后向前。通过先统计字符串...
剑指Offer(Python多种思路实现):树的子结构 面试26题: 题目:树的子结构 题:输入两棵二叉树A和B,判断B是不是A的子结构。 解题思路一:递归,注意空指针的情况。 class Solution: def HasSubtree(self, pRoot1, ...
面试题03 哈希表,代码鲁棒性 面试题04 利用递增的规律 面试题05 面试题11 剑指 Offer 21 双指针降低复杂度 剑指 Offer 29 模拟 剑指 Offer 39 利用性质:投票法 剑指 Offer 40 堆或者快排思想(☆) 剑指 Offer 41 ...
剑指Offer(Python多种思路实现):对称的二叉树 面试28题: 题目:对称的二叉树题: 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的 解题思路一:先...
剑指Offer(Python多种思路实现):复杂链表的复制 面试35题: 题目:复杂链表的复制 题:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为...
剑指Offer(Python多种思路实现):删除链表中的节点 面试18题: 题目:删除链表中的节点 题一:在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。 解题思路一:先...
剑指Offer(Python多种思路实现):环的入口节点 面试23题: 题目:如果一个链表中包含环,如何找出环的入口节点? 解题分析:其实此题可以分解为三个题目:1)如何判断一个链表中是否包含环?2)如何找到环的入口节点...
剑指Offer(Python多种思路实现):链表中倒数第k个节点 面试22题: 题目:链表中倒数第k个节点 题:输入一个链表,输出该链表中倒数第k个结点。 解题思路一:为了实现只遍历链表一次就能找到倒数第k个节点,我们可以...
剑指Offer(Python多种思路实现):调整数组的顺序使奇数位于偶数前面 面试21题: 题目:调整数组的顺序使奇数位于偶数前面 题一:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前...
剑指Offer(Python多种思路实现):二叉树的下一个节点 面试8题: 题目:二叉树的下一个节点 题目描述:给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点...
剑指Offer(Python多种思路实现):序列化二叉树 面试37题: 题:序列化二叉树 题目:请实现两个函数,分别用来序列化和反序列化二叉树 解题思路一:首先来看二叉树的序列化,二叉树的序列化就是采用前序遍历二叉树输出...
难度:中等 一、题目描述: ...由此引入三指针的解法 2、代码实现 class Solution: def nthUglyNumber(self, n: int) -> int: dp = [1 for _ in range(n)] # 三指针初始化 i2 = 0 i3 = 0 i5 = 0 f
《剑指offer》java代码实现,一本关于面试算法题经典的书。 《玩转算法面试》,慕课课程,对leetcode的题目分门别类进行讲解,讲的很好,力荐。 排序算法,快排,归并排序,堆排。 数据结构,目前有循环队列、AVL树...
剑指Offer03-找出数组中重复的数字 26.删除排序数组中的重复项 136.只出现一次的数字 二分查找 面试题10.01合并排序的数组 合并区间 互为子集 剑指offer9-用两个栈模拟队列 165-比较版本号 1-两数之和 2-两数相加 双...
面试24题: 题目:反转链表 题:输入一个链表,反转链表并输出反转后链表的头节点。 解题思路一:注意反转时出现断裂现象,定义3个指针,分别指向当前遍历到的节点pNode、它的前一个节点pPrev及后一个节点pNext。 ...