• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成
  • 链表是随机分布在内存堆区的
  • 节点：就是一个个结构体

与数组的区别：
数组是连续的内存，如果内存不够长就会出现数据超出内存的问题，链表就是为了解决这个问题

单向链表

单向链表图解

链表 - 图1
节点：一个一个的结构体

  1. struct node
  2. {
  3.     //数据域
  4.     int data;
  5.     //指针域
  6.     struct node* next;//next就是指向下一个节点，指向方式就是保存下一个节点的地址，他读取的下一个节点也是同个类型，所以这里的指针类型用结构体本身
  7. };

数据域：节点里面存储的数据
指针域：指向下一个节点的指针

单向链表基础操作练习

创建单向连续链表并输出

新建一条含有n个节点带头节点的单链表,从键盘上输入节点的数据并打印整条链表
样例输入
5
1 2 3 4 5
样例输出:
1 2 3 4 5

  1. #include<iostream>
  2. using namespace std;
  4. //循环写法
  5. struct node
  6. {
  7.     int data;
  8.     struct node* next;
  9. };
  11. //创建单向链表
  12. struct node* Create()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     struct node* head = (struct node*)malloc(sizeof(struct node));//在堆区新建一个头节点
  17.     head->next = NULL;//把头节点的下一个节点地址置空，防止指针指向野指针
  19.     //用last是因为head节点无法参与到后边节点的循环里，所用用last来承接，而且用last节点来循环遍历整个链，不会破坏原来节点的值
  20.     /*last要保证每次输入后都在最后的一个节点，last节点会与相同地址的节点关联
  21.     last步骤：
  22.     当last还没移动，last->next获取到了当前输入节点的地址，会把当前输入节点的地址传给相同地址的节点，
  23.     last下一步就会存入输入节点的地址，开始位移到当前输入的节点位置，重复上一步操作*/
  24.     struct node* last = head;
  26.     for (int i = 1; i < n; i++)
  27.     {
  28.         struct node* q = (struct node*)malloc(sizeof(struct node));//在堆区新建一个节点
  29.         cin >> q->data;//给当前节点输入一个值
  30.         q->next = NULL;//当前暂无下一个节点，指向空
  32.         //这两步不要反了，反了就不对了
  33.         last->next = q;//把当前输入节点的地址保存到last->next里，此时last的位置还在当前输入节点的上一个节点，last->next的地址会传给当前last对应节点的next里（也就是当前输入节点的上一个节点）
  34.         last = q;//让last的地址变为当前输入节点的地址，目的是让last能一直右移，保持在整段链表的最后
  35.     }
  36.     return head;
  37. }
  38. void Print(struct node* head)
  39. {
  40.     for (struct node* p = head->next; p != NULL; p = p->next)
  41.         cout << p->data << endl;
  42. }
  44. int main()
  45. {
  46.     struct node* head = Create();
  47.     Print(head);
  49.     return 0;
  50. }

链表 - 图2

从链表的头和尾插入新的节点

  1. #include <iostream>
  2. using namespace std;
  3. #pragma  warning(disable:4996)
  5. //节点类型
  6. struct node
  7. {
  8.     int data;
  9.     struct node* next;
  10. };
  12. //新建链表
  13. struct node* Create()
  14. {
  15.     int n;
  16.     cin >> n;
  17.     struct node* head = (struct node*)malloc(sizeof(struct node));
  18.     head->next = NULL;
  19.     struct node* last = head;
  20.     for (int i = 1; i <= n; i++)
  21.     {
  22.         struct node* q = (struct node*)malloc(sizeof(struct node));
  23.         cin >> q->data;
  24.         q->next = NULL;
  26.         last->next = q;
  27.         last = q;
  28.     }
  29.     return head;
  30. }
  32. //往链表的开头插入新节点,
  33. struct node* H_insert(struct node* head)
  34. {
  35.     struct node* q = (struct node*)malloc(sizeof(struct node));
  36.     cin >> q->data;
  37.     q->next = NULL;
  39.     //下面两句顺序不能搞反，否则会出现地址丢失问题
  40.     q->next = head->next;//新的节点的next接收head节点的next相当于新节点的尾与原本的第一个节点链接
  41.     head->next = q;//head的next接上新的节点就完成新节点插入头部的工作
  43.     return head;
  44. }
  46. //往链表的结尾插入新节点
  47. struct node* T_insert(struct node* head)
  48. {
  49.     //新增一个节点
  50.     struct node* q = (struct node*)malloc(sizeof(struct node));
  51.     cin >> q->data;//往节点输入一个值
  52.     q->next = NULL;//next指向空防止野指针
  54.     //把已有的链表遍历到最后一个节点
  55.     struct node* p = head->next;
  56.     while (p->next)
  57.         p = p->next;
  59.     //将新建的节点地址，赋给原本链表的最后一个节点的next指针
  60.     p->next = q;
  61.     return head;
  62. }
  64. //打印
  65. void Print(struct node* head)
  66. {
  67.     for (struct node* p = head->next; p != NULL; p = p->next)
  68.         cout << p->data << " ";
  69.     cout << endl;
  70. }
  72. int main()
  73. {
  74.     struct node* head = Create();
  75.     Print(head);
  76.     head = T_insert(head);
  77.     Print(head);
  78.     head = W_insert(head);
  79.     Print(head);
  80.     return 0;
  81. }

逆序输出链表

输入一行字符串，并以此建立一条带头节点的单链表，然后对该链表里的所有节点按输入时的逆序输出。
样例输入：
asdfg
样例输出：
gfdsa
也可以思考用递归做

  1. #include <iostream>
  2. using namespace std;
  3. #pragma  warning(disable:4996)
  5. struct node
  6. {
  7.     char data;
  8.     struct node* next;
  9. };
  11. //创建链表
  12. struct node* Create()
  13. {
  14.     char c = '\0';//创建字符‘\0’代表没有字符
  15.     struct node* head = (struct node*)malloc(sizeof(struct node));
  16.     head->next = NULL;
  18.     //链表逆序
  19.     while ((c = getchar()) != '\n')//\n是回车，getchar()是从键盘获取字符，当输入字符是回车时退出循环
  20.     {
  21.         //创建节点
  22.         struct node* q = (struct node*)malloc(sizeof(struct node));
  23.         q->data = c;//给节点变量赋值
  24.         q->next = NULL;指控指针，防止野指针
  26.         q->next = head->next;//head->next的地址赋给当前节点的next，由于下一行代码的head的next保存了前一个节点的地址，这里就相当于当前节点指向上一个节点
  27.         head->next = q;//用head的next接收当前节点的地址
  28.     }
  29.     return head;
  30. }
  32. void Print(struct node* head)
  33. {
  34.     struct node* p = head->next;
  35.     while (p)
  36.     {
  37.         putchar(p->data);//putchar()是输出字符的函数
  38.         p = p->next;
  39.     }
  40. }
  42. int main()
  43. {
  44.     struct node* head = Create();
  45.     Print(head);
  46.     return 0;
  47. }

链表 - 图3

逆序建立两条链表并合二为一

先后读入２行字符，按照输入时的逆序建立一条带头节点的单链表，先分别输出每行字符，
然后把２条链表合成一条链表，输出整个链表的节点信息。
样例输入：
asdfg
zxcv
样例输出：
gfdsavcxz

  1. #include <iostream>
  2. using namespace std;
  3. #pragma  warning(disable:4996)
  5. struct node
  6. {
  7.     char data;
  8.     struct node* next;
  9. };
  11. //创建单向列表并逆序
  12. struct node *Create()
  13. {
  14.     char c = '\0';
  15.     struct node* head = (struct node*)malloc(sizeof(struct node));
  16.     head->next = NULL;
  18.     while((c=getchar())!='\n')
  19.     {
  20.         struct node* q = (struct node*)malloc(sizeof(struct node));
  21.         q->data = c;
  22.         q->next = NULL;
  24.         q->next = head->next;
  25.         head->next = q;
  26.     }
  27.     return head;
  28. }
  30. struct node *Sum(struct node *head1,struct node *head2)
  31. {
  32.     struct node* p = head1->next;//创建节点p位置在第一个头节点的首节点
  33.     for (; p->next; p = p->next);//遍历head1的节点直到尾部
  34.     p->next = head2->next;//把head1的尾节点与head2开头的链表的首节点连起来
  35.     free(head2);//把head2释放，因为head2已经没有关联任何节点
  36.     return head1;
  37. }
  39. void Print(struct node *head)
  40. {
  41.     struct node* p = head->next;
  42.     while(p)
  43.     {
  44.         putchar(p->data);
  45.         p = p->next;
  46.     }
  47. }
  49. int main()
  50. {
  51.     struct node* head1 = Create();
  52.     struct node* head2 = Create();
  53.     Print(Sum(head1, head2));
  55.     return 0;
  56. }

删除单链表中某个元素

  1. #include <iostream>
  2. using namespace std;
  3. #pragma  warning(disable:4996)
  5. struct node
  6. {
  7.     char data;
  8.     struct node* next;
  9. };
  11. //创建单向链表
  12. struct node *Create()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     struct node* head = (struct node*)malloc(sizeof(struct node));
  17.     head->next = NULL;
  18.     struct node* last = head;
  19.     for (int i = 1; i <= n; i++)
  20.     {
  21.         struct node* q = (struct node*)malloc(sizeof(struct node));
  22.         cin >> q->data;
  23.         q->next = NULL;
  25.         last->next = q;
  26.         last = q;
  27.     }
  28.     return head;
  29. }
  31. //删除：值为3节点
  32. struct node* Delete(struct node* head)
  33. {
  34.     int data;
  35.     cout << "请输入要删除的值：";
  36.     cin >> data;
  38.     //创建两个节点来判断要删除的位置，用两个节点可以更好的做链接
  39.     struct node* pre = head;//创建一个节点，位置在head上
  40.     struct node* p = head->next;//创建一个节点在head链表的首节点上
  41.     while (p->next)
  42.     {
  43.          if (p != NULL && p->data == data)//判断当前节点的值是否与输入的值相等。相等且不为空则进入此行
  44.          {
  45.               pre->next = p->next;//
  46.                free(p);
  47.                p = pre->next;
  48.           }
  49.           else
  50.           {
  51.             //如果不满足上边条件，则pre和p个往前走一步
  52.                pre = pre->next;
  53.                p = p->next;
  54.           }
  55.      }
  56.      return head;
  57. }
  59. //打印链表
  60. void Print(struct node *head)
  61. {
  62.     for (struct node* p = head->next; p != NULL; p = p->next)
  63.         cout << p->data << " ";
  64.     cout << endl;
  65. }
  67. int main()
  68. {
  69.     struct node* head = Create();
  70.     Delete(head);
  71.     Print(head);
  73.     return 0;
  74. }

链表 - 图4

删除单链表中连续相同的数据

样例输入：
12
1 2 3 2 2 2 4 5 6 6 6 7
样例输出：
1 2 3 2 4 5 6 7

  1. #include <iostream>
  2. using namespace std;
  3. #pragma  warning(disable:4996)
  5. struct node
  6. {
  7.     char data;
  8.     struct node* next;
  9. };
  11. //创建链表
  12. struct node *Create()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     struct node* head = (struct node*)malloc(sizeof(struct node));
  17.     head->next = NULL;
  18.     struct node* last = head;
  19.     for (int i = 1; i <= n; i++)
  20.     {
  21.         struct node* q = (struct node*)malloc(sizeof(struct node));
  22.         cin >> q->data;
  23.         q->next = NULL;
  25.         last->next = q;
  26.         last = q;
  27.     }
  28.     return head;
  29. }
  31. //删除链表中连续相同的数据
  32. void Delet_link_same(struct node* head)
  33. {
  34.     struct node* pre = head->next;
  35.     struct node* p = pre->next;
  36.     while (p)
  37.     {
  38.         if (p->data == pre->data)
  39.         {
  40.             struct node* temp = p;
  41.             p = p->next;
  42.             free(temp);
  43.         }
  44.         else
  45.         {
  46.             pre->next = p;
  47.             pre = p;
  48.             p = p->next;
  49.         }
  50.     }
  51.     pre->next = NULL;
  52. }
  54. //打印链表
  55. void Print(struct node *head)
  56. {
  57.     for (struct node* p = head->next; p != NULL; p = p->next)
  58.         cout << p->data << " ";
  59.     cout << endl;
  60. }
  62. int main()
  63. {
  64.     struct node* head = Create();
  65.     Delet_link_same(head);
  66.     Print(head);
  68.     return 0;
  69. }

链表排序

从键盘上输入n个整数,并以此建立一条带头节点的单向链表,然后对链表中的数据进行升序排列,并输出
样例输入:
10
10 9 8 7 6 5 4 3 2 1
9 10
8 9
7 8
6 7
5 6
4 5
3 4
2 3
1 2
样例输出:
1 2 3 4 5 6 7 8 9 10

  1. #include <iostream>
  2. using namespace std;
  3. #pragma  warning(disable:4996)
  5. struct node
  6. {
  7.     char data;
  8.     struct node* next;
  9. };
  11. //创建链表
  12. struct node *Create()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     struct node* head = (struct node*)malloc(sizeof(struct node));
  17.     head->next = NULL;
  18.     struct node* last = head;
  19.     for (int i = 1; i <= n; i++)
  20.     {
  21.         struct node* q = (struct node*)malloc(sizeof(struct node));
  22.         cin >> q->data;
  23.         q->next = NULL;
  25.         last->next = q;
  26.         last = q;
  27.     }
  28.     return head;
  29. }
  31. //升序排列：把值进行交换就行
  32. void Sort(struct node* head)
  33. {
  34.     struct node* p, * q;
  35.     for(p=head->next;p;p=p->next)
  36.     {
  37.         for (q = p->next; q; q = q->next)
  38.         {
  39.             if (p->data > q->data)
  40.             {
  41.                 swap(p->data, q->data);
  42.             }
  43.         }
  44.     }
  45. }
  47. //打印链表
  48. void Print(struct node *head)
  49. {
  50.     for (struct node* p = head->next; p != NULL; p = p->next)
  51.         cout << p->data << " ";
  52.     cout << endl;
  53. }
  55. int main()
  56. {
  57.     struct node* head1 = Create();
  58.     struct node* head2 = Create();
  59.     Print(Sum(head1, head2));
  61.     return 0;
  62. }

单向循环链表图解

链表 - 图5

单循环链表练习

创建一个循环链表

#include <iostream>
using namespace std;
#pragma  warning(disable:4996)

struct node
{
    char data;
    struct node* next;
};

struct node* Create()
{
    //这里都是创建链表的过程
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    struct node* last = head;
    char c;
    while ((c = getchar()) != '\n')
    {
        struct node* q = (struct node*)malloc(sizeof(struct node));
        q->data = c;
        q->next = NULL;
        last->next = q;
        last = q;
    }

    //这里是创建环
    last->next = head; //闭环
    return head;
}

void Print(struct node* head)
{
    struct node* p = head->next;
    while (p != head)
    {
        cout << p->data;
        p = p->next;
    }
    cout << endl;
}
int main()
{
    struct node* head = Create();
    Print(head);
    return 0;
}

判断链表是否有环，环的入口

#include <iostream>
using namespace std;
#pragma  warning(disable:4996)

struct node
{
    char data;
    struct node* next;
};

struct node* Create()
{
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    struct node* last = head;
    char c;
    while ((c = getchar()) != '\n')
    {
        struct node* q = (struct node*)malloc(sizeof(struct node));
        q->data = c;
        q->next = NULL;
        last->next = q;
        last = q;
    }
    struct node* p = head->next->next->next->next; //第4个数据节点做为环形链表的入口

    last->next = p; //闭环
    return head;
}

//判断是否有环
//判断是否有环用两个节点来赛跑，一个节点走两步，一个节点走一步，如果有环，快的一定会追上慢的，否则永远追不上
struct node* ExitLoop(struct node* head)
{
    struct node* fast, * slow;
    fast = slow = head;//两个节点都从头节点出发
    while (slow && fast->next)
    {
        slow = slow->next;//slow每次走一步
        fast = fast->next->next;//fast每次走两步
        if (slow == fast)//fast追上slow证明有环
            return slow;
    }
    return NULL;
}

//找到环的入口点:从链表起点head到入口点的距离 == 相遇点到入口点的距离
struct node* FindLoopStart(struct node* head)
{
    struct node* p1 = head;//p1从链表的头开始
    struct node* p2 = ExitLoop(head);//p2从之前在环相遇的地方开始
    while (p1 != p2)//两节点相遇，就是环的起点
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

void Print(struct node* head)
{
    struct node* p = head->next;
    while (p != head)
    {
        cout << p->data;
        p = p->next;
    }
    cout << endl;
}

int main()
{
    struct node* head = Create();
    cout << FindLoopStart(head)->data << endl;
    //    Print(head);
    return 0;
}

双向链表

双向链表图解

链表 - 图6
双向链表节点：

struct node
{
    //数据域
    int data;
    //指针域
    struct node* prior//双向链表使用的，让链表从尾指向头
    struct node* next;
};

双向链表练习

创建双向链表

#include<iostream>
using namespace std;

struct node
{
    int data;
    struct node* next, * prior;
};

//创建链表
struct node* Create1()
{
    cout << "创建双向链表: ";
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    head->prior = NULL;
    struct node* last = head;//last从头开始出发
    char c = '\0';//初始化字符变量

    while ((c = getchar()) != '\n')//当输入是回车的时候退出循环
    {
        创建存有变量的节点
        struct node* p = (struct node*)malloc(sizeof(struct node));
        p->data = c;//存入变量
        p->next = NULL;
        p->prior = NULL;

        last->next = p;//用last来把last所在的节点与当前的节点p链接
        p->prior = last;让p链接last所在的节点，形成一个回链，达成双向链表的效果
        last = p;//把last的位置移动到当前p的位置
    }
    return head;
}

void Print1(struct node* head)
{
    cout << "正序：";
    struct node* p = head->next;//从首节点出发
    while (p)//当p指向空时停止循环
    {
        putchar(p->data);//输出字符
        p = p->next;//p一直往前走
    }
    cout << endl;
}
int main()
{
    struct node* head = Create1();
    Print1(head);

    return 0;
}

删除链表中第几个元素

#include<iostream>
using namespace std;

struct node
{
    int data;
    struct node* next, * prior;
};

struct node* Create1()
{
    cout << "创建双向链表: ";
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    head->prior = NULL;
    struct node* last = head;

    char c = '\0';
    while ((c = getchar()) != '\n')
    {
        struct node* p = (struct node*)malloc(sizeof(struct node));
        p->data = c;
        p->next = NULL;
        p->prior = NULL;

        last->next = p;
        p->prior = last;
        last = p;
    }
    return head;
}
void Print1(struct node* head)
{
    cout << "正序：";
    struct node* p = head->next;
    while (p)
    {
        putchar(p->data);
        p = p->next;
    }
    cout << endl;
}
struct node* DeleteNode(struct node* head)
{
    cout << "删除第几个节点：";
    int n;
    cin >> n;
    struct node* p = head;
    int i = 0;//计算循环次数，控制节点位移的位置
    while (p->next && i < n)//当p->next不是空时，i小于输入的节点位置就循环
    {
        p = p->next;//p一直走走到要删除的位置停下
        i++;
    }
    if (i == n)//当i等于n，表示到了删除的位置
    {
        if (p->next)
        {
            p->next->prior = p->prior;//p的下一个节点的prior的地址变为p上一个节点的地址
        }
        p->prior->next = p->next;//p上一个节点的next的地址变为p下一个节点的地址
        free(p);//释放p，删除p所在的节点
    }
    return head;
}
int main()
{
    struct node* head = Create1();
    DeleteNode(head);
    Print1(head);
    return 0;
}

逆序输出

#include<iostream>
using namespace std;

struct node
{
    int data;
    struct node* next, * prior;
};
struct node* Create2()
{
    cout << "创建双向链表: ";
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    head->prior = NULL;
    struct node* last = head;
    char c = '\0';

    while ((c = getchar()) != '\n')
    {
        struct node* p = (struct node*)malloc(sizeof(struct node));
        p->data = c;
        p->next = NULL;
        p->prior = NULL;

        last->next = p;
        p->prior = last;
        last = p;
    }
    return last;//last的位置就在整个链的最后，直接返回last做为头节点使用就可以倒序输出
}
void Print2(struct node* last)
{
    cout << "倒序：";
    struct node* p = last;//last做头节点
    while (p->prior)
    {
        //用prior就就可以从后往前走
        putchar(p->data);
        p = p->prior;
    }
    cout << endl;
}

int main()
{
    struct node* last = Create2();
    Print2(last);

    return 0;
}

插入元素，这个代码有问题要去问老师

#include<iostream>
using namespace std;

struct node
{
    int data;
    struct node* next, * prior;
};

struct node* Create1()
{
    cout << "创建双向链表: ";
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    head->prior = NULL;
    struct node* last = head;
    char c = '\0';

    while ((c = getchar()) != '\n')
    {
        struct node* p = (struct node*)malloc(sizeof(struct node));
        p->data = c;
        p->next = NULL;
        p->prior = NULL;

        last->next = p;
        p->prior = last;
        last = p;
    }
    return head;
}
void Print1(struct node* head)
{
    cout << "正序：";
    struct node* p = head->next;
    while (p)
    {
        putchar(p->data);
        p = p->next;
    }
    cout << endl;
}

struct node* InsertNode(struct node* head)
{
    cout << "在第几个节点后插入：";
    int n;
    cin >> n;

    struct node* q = (struct node*)malloc(sizeof(struct node));
    cout << "请输入要插入的值：";
    cin >> q->data;
    q->next = NULL;
    q->prior = NULL;

    struct node* p = head;
    int i = 0;
    while (p->next && i < n)
    {
        p = p->next;
        i++;
    }
    if (i == n)
    {
        if (p->next)
        {
            q->next = p->next;
            p->next->prior = q;
        }
        p->next = q;
        q->prior = p;
    }
    return head;
}

int main()
{
    struct node* head = Create1();
    InsertNode(head);
    Print1(head);

    return 0;
}

回文链表

请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true

#include<iostream>
using namespace std;

struct node
{
    char data;
    struct node* next, * prior;
};

//创建链表
void Create(struct node*& head, struct node*& last)//这里是为了把head和last都传下去，而不只是返回一个变量
{
    head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    head->prior = NULL;
    last = head;
    char c;
    while ((c = getchar()) != '\n')
    {
        struct node* q = (struct node*)malloc(sizeof(struct node));
        q->data = c;
        q->next = NULL;
        q->prior = NULL;

        last->next = q;
        q->prior = last;
        last = q;
    }
}

int Is_hw(struct node* head, struct node* last)
{
    struct node* p = head->next;
    struct node* q = last;
    for (; p != q && p != NULL; p = p->next, q = q->prior)//偶数个节点的时候p是不会等于q的，所以需要p!=NULL来限制
    {
        if (p->data != q->data)
            break;
    }
    if (p == q || p == NULL)
        return 1;
    else
        return 0;
}

int main()
{
    struct node* head, * last;
    Create(head, last);
    cout << Is_hw(head, last) << endl;

    return 0;
}

合并 k 个排序链表

合并 k 个排序链表，返回合并后的排序链表。
示例:
样例输入:
3
3
1 4 5
3
1 3 4
2
2 6
样例输出:
1 1 2 3 4 4 5 6

#include <iostream>
using namespace std;
#pragma  warning(disable:4996)

struct node
{
    int data;
    struct node* next;
};

void Create(struct node*& head, struct node*& last)//这里的&是引用
{
    head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    int n;
    cout << "输入节点个数:";
    cin >> n;
    last = head;
    cout << "输入节点数据:" << endl;
    for (int i = 1; i <= n; i++)
    {
        struct node* q = (struct node*)malloc(sizeof(struct node));
        cin >> q->data;
        q->next = NULL;
        last->next = q;
        last = q;
    }
}

void Print(struct node* head)
{
    struct node* p = head->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void Sort(struct node* head)
{
    struct node* p, * q, * min;
    for (p = head->next; p; p = p->next)
    {
        for (min = p, q = p->next; q; q = q->next)
        {
            if (min->data > q->data)
            {
                min = q;
            }
        }
        swap(p->data, min->data);
    }
}

int main()
{
    struct node* head1, * last1, * head2, * last2;
    int k;
    cout << "输入K的值:";
    cin >> k;
    Create(head1, last1);//struct node*& head=head1;
    struct node* p = last1;
    for (int i = 1; i < k; i++)
    {
        Create(head2, last2);
        p->next = head2->next;
        p = last2;
        free(head2);
    }
    Sort(head1);
    Print(head1);
    return 0;
}