C/C++链表操作(面试)
2023-09-11 14:16:38 时间
1.为了反转这个单链表,我们先让头结点的next域指向结点2,再让结点1的next域指向结点3,最后将结点2的next域指向结点1,就完成了第一次交换,顺序就变成了Header-结点2-结点1-结点3-结点4-NULL,然后进行相同的交换将结点3移动到结点2的前面,然后再将结点4移动到结点3的前面就完成了反转,思路有了,就该写代码了:
1 LinkedList ReverseSinglyLinkedList(LinkedList list) 2 { 3 LNode *tmp = NULL; 4 LNode *p = NULL; 5 6 if (list == NULL) 7 { 8 return NULL; 9 } 10 tmp = list->next; 11 while (tmp->next != NULL) 12 { 13 p = tmp->next; 14 tmp->next = p->next; 15 p->next = list->next; 16 list->next = p; 17 } 18 return list; 19 }
2.链表排序
相比较线性表的排序而言,链表排序的内容稍微麻烦一点。一方面,你要考虑数据插入的步骤;另外一方面你也要对指针有所顾虑。要是有一步的内容错了,那么操作系统会马上给你弹出一个exception。就链表的特殊性而言,适合于链表的排序有哪些呢?
(1)插入排序 (适合)
(2)冒泡排序 (适合)
(3)希尔排序 (适合)
(4)选择排序 (适合)
(5)快速排序 (不适合)
(6)合并排序 (不适合)
(7)基数排序 (不适合)
(8)堆排序 (不适合)
其实,一般来说。如果涉及到数据之间的相对关系调配,那么只适合线性排序;如果只是数据内容之间的相互交换,那么这种排序方法也比较适合链表的排序。快速排序、合并排序、堆排序都涉及到了中间值的选取问题,所以不大适合链表排序。
为了说明链表排序是怎么进行的,我们可以利用插入排序作为示例,描述链表是怎么进行插入排序的。
a)首先遍历节点,一边是排序好的节点,一边是待排序的节点
1 void sort_for_link_node(NODE** ppNode) 2 { 3 NODE* prev; 4 NODE* curr; 5 6 if(NULL == ppNode || NULL == *ppNode) 7 return; 8 9 curr = (*ppNode) ->next; 10 (*ppNode) ->next = NULL; 11 12 while(curr){ 13 prev = curr; 14 curr = curr->next; 15 insert_for_sort_operation(ppNode, prev); 16 } 17 18 return; 19 }
b)对于待插入的节点,选择合适的位置插入即可
1 void insert_for_sort_operation(NODE** ppNode, NODE* pNode) 2 { 3 NODE* prev; 4 NODE* cur; 5 6 /* 在第一个数据之前插入pNode */ 7 if(pNode->data < (*ppNode)->data){ 8 pNode->next = *ppNode; 9 *ppNode = pNode; 10 return; 11 } 12 13 cur = *ppNode; 14 while(cur){ 15 if(pNode->data < cur->data) 16 break; 17 18 prev = cur; 19 cur = cur->next; 20 } 21 22 pNode->next = prev->next; 23 prev->next = pNode; 24 return; 25 }
3.有序单链表的合并就是两个之前都已排好序的链表,将它们合并成一个链表。合并的过程中对于两个链表值相等的结点也要链到最终的链表中去。
1 struct Node{ 2 int data; 3 Node *next; 4 }; 5 6 typedef struct Node Node; 7 8 Node *Merge(Node *head1,Node *head2) 9 { 10 Node *p1 = NULL; 11 Node *p2 = NULL; 12 Node *head = NULL; 13 14 //找出两个链表中第一个结点较小的结点,head记录较小结点的头结点 15 if(head1->next->data < head2->next->data) 16 { 17 head = head1; 18 p1 = head1->next; 19 p2 = head2->next; 20 } 21 else 22 { 23 head = head2; 24 p2 = head2->next; 25 p1 = head1->next; 26 } 27 28 Node *pcur = head; 29 30 //在两个链表中遍历比较,将值较小的结点链接到pcur结点后 31 while(p1 != NULL && p2 != NULL) 32 { 33 if(p1->data <= p2->data) 34 { 35 pcur->next = p1; 36 pcur = p1; 37 p1 = p1->next; 38 } 39 else 40 { 41 pcur->next = p2; 42 pcur = p2; 43 p2 = p2->next; 44 } 45 } 46 //将p1或p2剩余的结点链到pcur之后,完成整个合并的过程 47 if(p1 != NULL) 48 pcur->next = p1; 49 if(p2 != NULL) 50 pcur->next = p2; 51 52 return head; 53 }
相关文章
- [C/C++基础知识] 那些被遗忘的链表知识
- 链表数据结构(C/C++语言实现)
- C语言/C++基础之元旦新年倒计时程序包含天、时、分、秒(附源码)
- C语言/C++常见习题问答集锦(七十一) 之创建链表与洗牌发牌
- C语言/C++常见习题问答集锦(六十二) 之约瑟夫环问题(C语言链表实现)
- C语言/C++常见习题问答集锦(四十八) 之字符替换与整数拆分
- Open3D(C++) 计算三角形面积
- C/C++ Qt ListWidget 列表框组件应用
- C++设计模式:迭代器模式
- 静态链表的C++实现
- C++学习心得与c语言到c++衔接技巧
- 解答私信@被c++折磨头秃的花季美少女 //C++ 编写一个进阶版的进制转换程序,运行功能如下:请选择要输入的数字的进制(2、8、10、16):请输入该数字:请选择要转换成的进制(2、8。。。
- 解答私信@被c++折磨头秃的花季美少女 //C++ 写一个带命令行参数的程序,可以实现将参数求和、求平均值以及排序之后输出(参数的数量不确定)。
- c++ vector 初始化_C++--vector()的用法
- C++:读写二进制bin文件到double数组
- c++ static 静态变量初始化
- C# 与C/C++相互调用
- C++链表实现
- PAT 1013 C++ 版
- 循环队列---c++版本
- 滑动窗口(C++,Java)
- c++封装继承多态实例
- 使用Dependency Walker和dumpbin工具定位C++软件启动时找不到接口的报错问题