＜链表＞找到链表中的中心点

找到链表中的中心点奇数：m/2 = n , mid = n +1思想是确定当前共有多少个节点当节点个数多时不能采用遍历直到指针域指向空的方法o(n)快慢指针两个指针从起点开始移动，A走两个节点，B走1个节点。当A走到终点时B走到中点循环退出条件：奇数：快指针:p_fast->p_next = NULL偶数：快指针：P_fast = NULL↓_p_fast = p_slow↓_head                                     ↓_tail[数据1|P_next] [数据2|P_next] [数据3|P_next] [数据4|P_next] Null↑_P_node1   ↓_↑            ↓_↑           ↓_↑           ↓_↑↓_p_fast↓_head         ↓_p_slow                       ↓_tail[数据1|P_next] [数据2|P_next] [数据3|P_next] [数据4|P_next] Null↑_P_node1   ↓_↑            ↓_↑            ↓_↑           ↓_↑↓_p_fast↓_head                       ↓_p_slow       ↓_tail[数据1|P_next] [数据2|P_next] [数据3|P_next] [数据4|P_next] Null↑_P_node1   ↓_↑            ↓_↑            ↓_↑           ↓_↑找链表中倒数第n个元素快指针先走n-1步，此时慢指针还在头节点，快指针和满指针同时走，一直到快指针走到尾节点循环终止条件：快指针的p_next == NULL;找链表中倒数第2个元素:↓_p_fast = p_slow↓_head                                     ↓_tail[数据1|P_next] [数据2|P_next] [数据3|P_next] [数据4|P_next] Null↑_P_node1   ↓_↑            ↓_↑            ↓_↑           ↓_↑↓_p_slow       ↓_p_fast↓_head                                      ↓_tail[数据1|P_next] [数据2|P_next] [数据3|P_next] [数据4|P_next] Null↑_P_node1   ↓_↑            ↓_↑            ↓_↑           ↓_↑
.......↓_p_slow      ↓_p_fast↓_head                                      ↓_tail[数据1|P_next] [数据2|P_next] [数据3|P_next] [数据4|P_next] Null↑_P_node1   ↓_↑            ↓_↑            ↓_↑           ↓_↑

#include "find_mid_last.h"
#include 
using namespace std;int main(void)
{struct Node* p_head1 = NULL;create_list(1);create_list(3);create_list(5);create_list(7);// 把上面链表的头指针指向的地址赋值给新指针p_head1 = p_head;cout << "链表一："<< endl;print_linklist(p_head1);cout  << endl;p_head = NULL;struct Node* p_head2 = NULL;create_list(1);create_list(4);create_list(6);create_list(8);create_list(9);create_list(10);// 把上面链表的头指针指向的地址赋值给新指针p_head2 = p_head;cout << "链表二："<< endl;print_linklist(p_head2);cout  << endl;p_head = NULL;merge_linklist(p_head1, p_head2);// 打印合并后的值cout << "合并两个链表：" << endl;print_linklist(p_head);cout  << endl;delete_repeat(p_head);cout << "删除合并后重复的内容：" << endl;print_linklist(p_head);cout  << endl;cout << "找到中间节点的elem = " << find_mid(p_head) << endl;cout << "找到倒数第3个节点的elem = " << find_last_nth(p_head, 3) << endl;return 0;
}

find_mid_last.cpp

#include 
#include "find_mid_last.h"
using namespace std;// 头指针指向整个链表的第一个节点的地址，插入数据时，不可移动
struct Node* p_head = NULL;
// 不断追加数据时需要尾指针，始终指向链表的末尾，插入数据时，可以移动
struct Node* p_tail = NULL;// 创建节点
void create_list(unsigned int elem)
{// 节点的数据占用多大的空间就开辟多大的内存空间，返回void* 类型，需要强制转换为节点的类型struct Node* p_node = (struct Node *)malloc(sizeof(struct Node));// 节点地址被赋值给指针P// 初始化数据域p_node->elem = elem;// 初始化指针域，此时并没有串联节点，指针指向空p_node->p_next = NULL;// 若一个节点都没有放到链表中if(p_head == NULL)p_head = p_node;// 插入数据时，不可移动else// 第二次调用时：P_tail = p_node1 = 第一个节点的地址，相当于第一个节点的指针域指向第二个节点的节点地址(p_node1->p_next = p)p_tail->p_next = p_node;// 第一次赋值的是第一个节点地址(只有一个元素：头=尾)，第二次赋值的是第二个节点地址p_tail = p_node;/*
第一次调用create_list↓_head = P_node1      ↓_tail = P_node1[数据1|指针]  Null↑       ↓___↑P_node1 P_next第二次调用create_list↓_head    ↓_tail = P_node1[数据1|指针] [数据2|指针]  Null↑       ↓___↑      ↓___↑P_node1 P_next = P_node2
...........
*/
}// 在链表中插入节点：1.插入的位置，插入的值
void insert_node(int pos, unsigned int elem)
{// 前节点struct Node *pre;// 初始化前节点，从头开始pre = p_head;// 循环次数int i = 0;struct Node* p_new = (struct Node *)malloc(sizeof(struct Node));// 如果插入的位置是头节点 ，头节点没有前节点，if(pos == 0){p_new->elem = elem;// 新节点的指针域指向头节点(原来头节点的地址)p_new->p_next = p_head;// 更新“让新节点作为头节点p_head = p_new;}else{// 遍历链表，从头开始找，直到找到指定位置的前节点// 如找到位置3，则循环两次，循环次数 = 位置 -1while(i < pos - 1){pre = pre->p_next;i++;}// 1.跳出循序找到前节点p_new->elem = elem;// 2.前节点的指针域赋值(pos后节点的地址)给新节点的指针域p_new->p_next = pre->p_next;// 3.让pos前节点的指针域指向新节点的地址pre->p_next = p_new;// 链表末尾if(p_new->p_next == NULL)// 更新p_tail = p_new;}
}void delete_node(int pos)
{// 前节点，要删除的节点struct Node *pre, *p_delet;pre = p_head;int i = 0;// 删除头节点if(pos == 0){// 更新p_head = p_head->p_next;// 释放头节点free(pre);}else{while(i < pos - 1){pre = pre->p_next;i++;}// 1.找到前节点// 2.前节点的指针域指向的是要删除的节点的地址p_delet = pre->p_next;// 3.让pos前节点的指针域指向要删除的节点地址(pos的后节点)，相当于删除pre->p_next = p_delet->p_next;// 删除尾节点if(p_delet->p_next == NULL)p_tail = pre;// 更新// 释放当前要删除节点所占用的内存空间free(p_delet);}
}// 显示链表数据域
void print_linklist(struct Node* linlist_head)
{struct Node *p;// p不为空的话就一直更新p的位置for(p = linlist_head; p; p = p->p_next)cout << p->elem << " ";cout << endl;
}// 链表不像数组那样通过索引快速查找，需要遍历每一个元素，链表的优势在于：增、删
int search(unsigned int elem)
{struct Node *p;for(p = p_head; p; p = p->p_next)if(p->elem == elem)return 1;return 0;
}void merge_linklist(struct Node* p, struct Node* q)
{// p和q只要有一个为空就退出循环while(p && q){if(p->elem <= q->elem){// 若一个节点都没有放到链表中if(p_head == NULL)// 更新头p_head = p;// 第一次之后都不更改，不可移动else// 第二次赋值时：P_tail = p_node1，相当于p_node1->p_next = p_2p_tail->p_next = p;// 第一次赋值的是第一个节点地址(只有一个元素：头=尾)，第二次赋值的是第二个节点地址p_tail = p;// 更新p，指向下一个节点p = p->p_next;}else{if(p_head == NULL)p_head = q;elsep_tail->p_next = q;// 更新尾指针p_tail = q;// 更新qq = q->p_next;}}// 还剩9和10没有添加到节点数据域，若p为空(false)则取q，不为空(true)则取pp_tail->p_next = p ? p : q;// 指向9，9又关联10}// 入参：删除哪一个链表中的重复的节点
void delete_repeat(struct Node* head)
{int flag[11] = {0,0,0,0,0,0,0,0,0,0};// 定义一个指针指向数组的节点struct Node* p = head;struct Node* p_delete = NULL;// 肯定有第一个节点，第一个节点肯定出现过，不然为空flag[p->elem] = 1;// 如果下一个节点存在while(p->p_next != NULL){// 如果下一个节点没有被标记if(flag[p->p_next->elem] == 0){// 标记flag[p->p_next->elem] = 1;// 更新到下一个节点p = p->p_next;}else// 如果有重复元素：flag[i] = flag[j]{// 把前操作节点(p_next)的地址赋值给上上节点的p_next，就相当于删除上一个节点p_delete = p->p_next;p->p_next = p_delete->p_next;free(p_delete);}}}int find_mid(struct Node* head)
{// 定义快慢指针struct Node* p_fast;struct Node* p_slow;// 初始化p_fast = p_slow = p_head;while(p_fast != NULL && p_fast->p_next != NULL){// 每次更新两个节点p_fast = p_fast->p_next->p_next;// 每次更新一个节点p_slow = p_slow->p_next;}return p_slow->elem;
}int find_last_nth(struct Node* head, int n)
{struct Node* p_fast;struct Node* p_slow;p_fast = p_slow = head;int i;// 快指针先走n-1步for(i = 0; i < n-1; i++){p_fast = p_fast->p_next;}// 快指针和满指针同时走，一直到快指针走到尾节点while(p_fast->p_next != NULL){p_fast = p_fast->p_next;p_slow = p_slow->p_next;}return p_slow->elem;}

find_mid_last.h

#ifndef LINKLIST_H__
#define LINKLIST_H__#include // 声明一个外部变量，在其他文件可见可赋值
extern struct Node* p_head;
extern struct Node* p_tail;struct Node
{// 数据域unsigned int elem;// 指针域struct Node* p_next;
};void create_list(unsigned int elem);
void merge_linklist(struct Node* p, struct Node* q);void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct Node* linlist_head);
int search(unsigned int elem);
void delete_repeat(struct Node* head);
int find_mid(struct Node* head);
int find_last_nth(struct Node* head, int n);#endif

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！