问题描述:假设有一个没有头指针的单链表。一个指针指向此单链表中间的一个节点(不是第一个,也不是最后一个节点),请将该节点从单链表中删除。
一般链表的删除需要顺着头结点向下找到当前待删节点的前驱节点,然后让前驱节点指向后驱节点就行了。这里,没有头结点,就没办法找到前驱结点。但我们可以采用“狸猫换太子”的做法。我们把当前结点“看成”是前驱结点,把后续节点当做待删结点删除(删除之前,记下后续结点的值),只需要让当前结点指向后驱结点的后驱结点。最后把后续结点值赋给当前结点的值。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct node{
int data;
node *next;
}Node;
void printlist(Node *head_ptr);
void delete_random_node(Node *current);
int main(){
Node n1, n2, n3;
n1.data = 10;
n1.next = &n2;
n2.data = 20;
n2.next = &n3;
n3.data = 30;
n3.next = NULL;
printf("Before deleting\n");
printlist(&n1);
delete_random_node(&n2);
printf("\nAfter deleting\n");
printlist(&n1);
return 0;
}
void printlist(Node *head_ptr){
Node *ptr = head_ptr;
while(ptr != NULL){
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}
void delete_random_node(Node *current){
assert(current != NULL);
Node *next = current->next;
if(next != NULL){
current->next = next->next;
current->data = next->data;
}
}
扩展问题
编写一个函数,给定一个链表的头指针,要求只遍历一次,将单链表中的元素顺序反转过来。
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
node *next;
}Node;
Node *reverse_linklist(Node *head);
void printlist(Node *ptr);
int main(){
Node n1, n2, n3;
Node *head;
head = (Node *)malloc(sizeof(Node));
head->next = &n1;
n1.data = 10;
n1.next = &n2;
n2.data = 20;
n2.next = &n3;
n3.data = 30;
n3.next = NULL;
printf("Before reversing\n");
printlist(head);
printf("\nAftering reversing\n");
printlist(reverse_linklist(head));
return 0;
}
void printlist(Node *head_ptr){
Node *ptr = head_ptr->next;
while(ptr != NULL){
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}
Node *reverse_linklist(Node *head){
Node *p = head->next;
Node *e = NULL;
Node *q;
while(p->next != NULL){
q = p->next;
p->next = e;
e = p;
p = q;
}
p->next = e;
head->next = p;
return head;
}
分享到:
相关推荐
从单链表中删除节点数值作为函数参数C和指针第十二章编程练习5,VC6.0编译通过
无头节点单链表的实现可是说是对C语言指针一个最直接、最贴合实际、也是最具有归纳性的程序设计应用。许多C语言基础面试题都涉及单链表的实现和构造,其目的就是考察面试者对C语言基础数据类型是否有足够的了解,对...
从单链表中删除节点指向欲删除的结点的指针作为函数参数C和指针第十二章编程练习5,VC6.0
头插法建立带头结点的单链表,并找出中间节点值
将两个单链表中的节点交错合并成一个.cpp
单链表交换节点排序,包括选择法、比较法、排序法。
快速找到未知长度单链表的中间节点 普通的方法很简单,首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为O(L+L/2)=O(3L/2)。
(1) 新节点的 pNext 指向原来的第一个节点的首地址, 即新节点和原来的 第一个节点 相连。 (2) 头结点的 pNext 指向新节点的首地址, 即头结点和新节点相连。 经过这两步新节点就插入了头结点和原来的第一个节点...
代码中包含单链表的常用操作,主要实现以下六个算法: 1.单链表的就地反转 2.链表相交或求公共起始节点 3.求链表倒数第n个节点 4.删除单个节点 5.判断链表是否有环 6.将2个递增的链表合并为递减链表 并全部调试通过...
重学数据结构第一步:简单实现下链表,功能不是很完善,重在学习思想。
cout请输入单链表的长度:"; cin>>length; for(int i=0;i;i++) { a[i]=i+1; } cout; LinkList<int> list(a,length); cout单链表为:"; list.display(); l=list.length() ; cout单链表长度为:"; list....
设计算法,将给定二叉树的叶子结点连成一个带头结点的单链表,并要求叶子结点按照从左到右的顺序插入,而排列顺序为从右到左(逆置)的单链表。
C语言实现单链表(常规操作) LinkList CreateHeadListH(); // 头插法创建单链表 LinkList CreateHeadListT(); // 尾插法创建单链表 int ListEmpty(); // 单链表判空 int ListLength(); // 求单链表长度...
数据结构单链表练习:删除单链表的倒数第n个节点。 博客地址:https://blog.csdn.net/qq_39400324/article/details/122640229
每敲一次代码都会有新的收获,基本功不扎实啥也干不了。单向链表的插入,删除,创建,遍历是数据结构的基本操作。里边的算法值得学习。下面我们就来学习一下单向链表结点的逐个删除的方法。
4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。 7.单链表交换任意两个元素(不包括表头) 8.判断...
单链表的建立、插入节点、删除节点、逆序、查找等等,希望了可以给你们带来帮助
删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。 7.单链表交换任意两个元素(不包括表头) 8.判断...
单链表的相关操作 1.1:单链表增加一个元素 1.2:单链表删除指定位置的元素(删除某个元素) 1.3:单链表打印 1.4:单链表的反转 1.5:单链表找出倒数第k个节点的元素 ... 1.7:找出单链表中中间节点的值
Python 数据结构 10单链表删除节点.mp4