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

找到链表中的中心点
  奇数：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 <iostream>
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 <iostream>
#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，则循环两次，循环次数 = 位置 -1
        while(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_2
                p_tail->p_next = p;

            // 第一次赋值的是第一个节点地址(只有一个元素：头=尾)，第二次赋值的是第二个节点地址
            p_tail = p;
            // 更新p，指向下一个节点
            p = p->p_next;
        }
        else
        {
            if(p_head == NULL)
                p_head = q;
            else
                p_tail->p_next = q;
            // 更新尾指针
            p_tail = q;
            // 更新q
            q = q->p_next;
        }
    }

    // 还剩9和10没有添加到节点数据域，若p为空(false)则取q，不为空(true)则取p
    p_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 <iostream>

// 声明一个外部变量，在其他文件可见可赋值
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