include<iostream>

using namespace std;

//单链表

typedef struct Lnode{

int data;

struct Lnode *next;

}Lnode;

//双链表

typedef struct DLnode{

int data;

struct DLnode *next;

}DLnode;

/*

尾插法建立单链表

*/

Lnode * Create(Lnode *head, int *a, int n){

Lnode *first, *node;

first = (Lnode *)malloc(sizeof(Lnode)); //头结点

head = first;

first->next = NULL;

for (int i = 0; i < n; ++i){

node = (Lnode *)malloc(sizeof(Lnode));

node->data = *(a + i);

first->next = node;

first = first->next;

}

first->next = NULL;

return head;

}

/*

头插法建立单链表

*/

Lnode * HeadCreate(Lnode *head, int *a, int n){

Lnode *first, *node;

first = (Lnode *)malloc(sizeof(Lnode)); //头结点

head = first;

first->next = NULL;

for (int i = 0; i < n; ++i){

node = (Lnode *)malloc(sizeof(Lnode));

node->data = *(a + i);

node->next = first->next;

first->next = node;

}

return head;

}

/*

在指定位置插入节点val

*/

Lnode * Insert(Lnode * head, int n, int val){

Lnode *p = head;

Lnode node = (Lnode)malloc(sizeof(Lnode));

for (int i = 0; i < n - 1; ++i){

p = p->next;

}

node->data = val;

node->next = p->next;

p->next = node;

return head;

}

/*

删除 data 为val的某个节点

*/

int Del(Lnode *head, int val){

Lnode*p, *q;

p = head; //传入头指针，然后p保存头指针信息，修改p,即等同于修改head头指针

while (p->next != NULL){ //p指向删除节点的前一个节点

if (p->next->data == val)

{

break;

}

p = p->next;

}

if (p->next == NULL){

return 0;

}

else{

q = p->next;

p->next = q->next;

free(q);

return 1;

}

}

/*

单链表反转

*/

Lnode* Reverse(Lnode *head){

Lnode *first = head->next, *tmp;

head->next = NULL;

while (first != NULL)

{

tmp = first->next;

first->next = head->next;

head->next = first;

first = tmp;

}

return head;

}

/*

• 构建有环单链表

*/

Lnode *CirLnode(Lnode *head, int num) {

Lnode *tmp, *tail;

tmp = tail = head->next;

for (int i = 1; i < num; ++i) {

tmp = tmp->next;

}

while (tail->next != NULL) {

tail = tail->next;

}

tail->next = tmp;

return head;

}

/*

• 判断单链表是否有环

*/

int IsCir(Lnode *head) {

Lnode *first, *last;

first = head;

last = head;

while (last != NULL && last->next != NULL) {

last = last->next->next;

first = first->next;

if (first == last) {

cout << first->data << endl; //在环中相遇的点,不一定是环的初始点

//求环的初始点

first = head;

while (first->next!=NULL){ //first和last在环中相遇的时候，使first指针回到head节点，last不动，然后first和last都每次走一步，两者再次相遇的点就是环的初始节点

first = first->next;

last = last->next;

if (first == last){

cout << "初始环点" << first->data << endl;

break;

}

}

return 1;

}

}

return 0;

}

/*

约瑟夫环问题

*/

int JoseCircle(Lnode *head,int num){

Lnode p = head,tmp,*q;

int i = 1;

q = p->next;

while (p!=q){

i++;

p = q;

q = q->next;

if (i == num){

tmp = q;

p->next = tmp->next;

q = p->next;

free(tmp);

i = 1;

}

}

return q->data;

}

/*

查找单链表中的倒数第K个结点（k > 0）

*/

int FindLast(Lnode * head, int k){

Lnode *p, *q;

q = head;

p = q->next;

for (int i = 0; i < k; ++i){ //使用两个指针，前面的指针走到正K，后面的指向第一个，两者相差为k-1,然后同时走，直到前面走到最后，后指针的位置即为所求

q = q->next;

}

if (q == NULL){ //k大于链表个数

return -1;

}

while (q->next != NULL){

p = p->next;

q = q->next;

}

/*

while(p){

p=p->next;

i++;

if(i>k) q=q->next; //p先走，只有存在p走过了K个节点，q才开始走，当p走到终点，q指向倒数K个节点

}

if(q==head) return 0; //q要么指向头结点，要么指向倒数第K个

else cout<<q->data<<endl;

*/

return p->data;

}

/*

• 删除相同节点

*/

Lnode *DelSame(Lnode *head) {

Lnode *p, *q, *tmp;

p = head->next;

while (p != NULL) {

q = p;

while (q->next != NULL) {

if (q->next->data == p->data) {

tmp = q->next;

q->next = tmp->next;

free(tmp);

}

else{

q = q->next;

}

}

p = p->next;

}

return head;

}

/*

查找单链表的中间节点

*/

int FindMid(Lnode *head){

Lnode *p, *q;

p = q = head->next;

while (q->next != NULL){

if (q->next->next != NULL){

p = p->next;

q = q->next->next;

}

else{

break;

}

}

return p->data;

}

/*

统计节点的个数

*/

int CalcNum(Lnode *head){

int n = 0;

Lnode *tmp = head;

if (head->next == NULL){

return n;

}

else{

while (tmp->next != NULL){

n++;

tmp = tmp->next;

}

return n;

}

}

/*

• 合并两个有序链表

*/

Lnode *MergeLnode(Lnode *h1, Lnode *h2) {

Lnode *p1, *p2, *p3, *q;

p1 = h1->next, p2 = h2->next;

q = p3 = h1;

q->next = NULL;

while (p1 != NULL && p2 != NULL) {

if (p1->data <= p2->data) {

q->next = p1;

p1 = p1->next;

}

else {

q->next = p2;

p2 = p2->next;

}

q = q->next;

}

if (p1 != NULL) q->next = p1;

if (p2 != NULL) q->next = p2;

return p3;

}

/*

• 求A,B链表的差集A-B

*/

Lnode *Diff(Lnode *h1, Lnode *h2) {

Lnode *p = h1, *q = h2;

Lnode *tmp;

while (p->next != NULL && q->next != NULL) {

if (p->next->data < q->next->data) {

p = p->next;

}

else if (p->next->data > q->next->data) {

q = q->next;

}

else {

tmp = p->next;

p->next = tmp->next;

free(tmp);

}

}

return h1;

}

/*

求A,B链表的交集

*/

void Common(Lnode *h1, Lnode *h2){

Lnode *p = h1, *q = h2;

while (p->next != NULL && q->next != NULL) {

if (p->next->data < q->next->data) {

p = p->next;

}

else if (p->next->data > q->next->data) {

q = q->next;

}

else {

cout << p->next->data << " ";

p = p->next;

q = q->next;

}

}

cout << endl;

}

/*

删除单链表中的最小值节点

*/

Lnode *DelMin(Lnode *head){

Lnode *q = head->next, min = q,tmp=head;

while (q != NULL && q->next!=NULL){

if (q->next->data < min->data){

tmp = q;

min = q->next;

}

q = q->next;

}

tmp->next = min->next;

free(min);

return head;

}

/*

将A链表拆分成A,B，其中A是data为奇数的点，B是data为偶数的点，顺序不变

*/

Lnode * SplitLink(Lnode *h1, Lnode *h2){

Lnode p = h1,t ;

Lnode *q = (Lnode *)malloc(sizeof(Lnode));

h2 = q;

q->next = NULL;

while (p->next != NULL){

if (p->next->data % 2 == 0){ //如果是偶数，就取出 放到B中，否则就继续前进，然后A就剩余奇数

t = p->next;

p->next = t->next;

t->next = NULL;

q->next = t;

q = q->next;

}

else{

p = p->next;

}

}

return h2;

}

/*

按照val值将单链表分成左右部分，左边比它小，右边比它大

*/

Lnode * Partation(Lnode *head,int val){

Lnode *p = head;

Lnode *small, *equal, *big; //将单链表拆成三个链表， 分别定义三个头指针，

small = equal = big = NULL;

Lnode * smallA, *equalA, *bigA ; //三个链表的尾指针

smallA = equalA = bigA = NULL;

while (p->next!=NULL){

if (p->next->data < val){

if (small == NULL){ //初始时，头尾指针均指向第一个进入大，等，小的节点

smallA = small = p->next;

}

else{

smallA->next = p->next; //不是第一个节点的时候，采用尾插法将节点插入链表

smallA = smallA->next;

}

}

else if (p->next->data == val){

if (equal == NULL){

equalA = equal = p->next;

}

else{

equalA->next = p->next;

equalA = equalA->next;

}

}

else {

if (big == NULL){

bigA = big = p->next;

}

else{

bigA->next = p->next;

bigA = bigA->next;

}

}

p = p->next;

}

if (small!=NULL && equalA != NULL) { //当小链表不为空，且等链表不为空，链接两个链表，等链表后置为空

equalA->next = NULL;

smallA->next = equal;

}

if (equalA!=NULL && bigA != NULL) { // 同理链接等链表和大链表

bigA->next = NULL;

equalA->next = big;

}

head->next = small != NULL ? small : equal != NULL ? equal : big;

return head;

}

/*

正序打印单链表

*/

void show(Lnode * head){

while (head->next != NULL){

cout << head->next->data << " ";

head = head->next;

}

cout << endl;

}

/*

逆序打印单链表

*/

void ShowTail(Lnode *head) { //print from tail,颠倒顺序的问题,采用栈,并且去掉头结点

Lnode *p = head;

if (p == NULL) {

return;

}

ShowTail(p->next);

cout << p->data << " ";

}

void tt(int *p){

int a = 3;

int *q = p;

q = &a;

}

void test(Lnode *head){ //一个单链表，first指针在前，last指针在后，first置空后，last便访问不到first后的节点

//last置空后，并不妨碍first访问后面的节点

Lnode *p = head->next;

Lnode *q = p;

p = p->next->next;

p->next = NULL;

q = q->next;

cout << p->data << endl;

}

void main(){

int a[] = {2,1,3,5,4};

int b[] = { 3,4, 5, 6, 7, 8 };

int lenA = sizeof(a) / sizeof(a[0]);

int lenB = sizeof(b) / sizeof(b[0]);

Lnode *head = NULL, *tail = NULL , *h2=NULL; //头指针

head = Create(head, a, lenA); //指针作为函数参数时，传递的也是指针的地址拷贝，所以指正不会改变，传入堆指针时，指针的值才会变化

show(head);

tail = HeadCreate(tail, b, lenB);

Reverse(tail);

show(tail);

/*

cout << "节点个数为: " << CalcNum(head) << endl;

*tail = Reverse(tail);

show(tail);

if (Del(head, 4) > 0){

cout << "找到并删除" << endl;

show(head);

}

Insert(head, 3, 6);

show(head);

cout << "节点个数为: " << CalcNum(head) << endl;

cout << FindMid(head) << endl;

head = DelMin(head);

show(head);

h2=SplitLink(head, h2);

show(head);

show(h2);

int *p = (int *)malloc(sizeof(int));

tt(p);

if (p == NULL){

cout << "null" << endl;

}

else{

cout << " not null" << endl;

}

*/

//head = CirLnode(head, 1);

/*if (IsCir(head)){

cout << "has a circle " << endl;

}

else{

cout << "no circle " << endl;

}*/

//cout << "Last out " << JoseCircle(head, 3) << endl;

//Common(head, tail);

head = Partation(head, 2);

show(head);

free(head);

free(tail);

system("pause");

}