学步园

#include <iostream>  
#include <string>  
using namespace std;  
  
struct Node  //一个链表的结点结构
{  
  int data ;  
  Node *next ;  
};  
typedef struct Node Node ;  
  
void traverse(Node *head);//遍历链表
Node * reverse(Node * head); //已知链表的头结点head,写一个函数把这个链表逆序
Node * merge(Node *head1, Node * head2);//合并链表，结果有序排列
Node *merge_recursive(Node *head1, Node *head2);//递归有序合并链表
int get_len(Node *head);//获得链表的长度

Node * reverse(Node * head) { 
    if(head == NULL)  
        return head;  
  
    Node *p = head->next;  
    if(p == NULL)  
        return head;  
  
    Node *q = p->next;  
    if(q == NULL) {  
        head->next = NULL;  
        p->next = head;  
        return p;  
    }  
  
    head->next = NULL;  
    while(q) {  
        p->next = head;  
        head = p;  
        p = q;  
        q = q->next;  
    }  
    p->next = head;  
    return p;  
}  
  
Node * merge(Node *head1, Node * head2) {  
    if(head1 == NULL)  
        return head2;  
      
    if(head2 == NULL)  
        return head1;  
  
    Node *p = NULL; //开头较小的  
    Node *q = NULL; //开头较大的  
    Node *head = NULL; //返回的  
    Node *qprev = NULL;  
    Node *pprev = NULL;  
  
    if(head1->data <= head2->data) {  
        p = head1;  
        q = head2;  
        head = head1;  
    }  
    else {  
        p = head2;  
        q = head1;  
        head = head2;  
    }  
    //拆散q到p  
    while(p && q) {  
        if(p->data <= q->data) {  
            pprev = p;  
            p = p->next;  
        }  
        else {  
            qprev = q;  
            q = q->next;  
              
            pprev->next = qprev;  
            qprev->next = p;  
  
            pprev = qprev;  
        }  
    }  
  
    return head;  
}  
  
Node *merge_recursive(Node *head1, Node *head2) {  
    Node *head = NULL;  
  
    if(head1 == NULL)  
        return head2;  
    if(head2 == NULL)  
        return head1;  
  
    if(head1->data <= head2->data) {  
        head = head1;  
        head->next = merge_recursive(head1->next, head2);  
    }  
    else {  
        head = head2;  
        head->next = merge_recursive(head1, head2->next);  
    }  
    return head;  }
node *sort(node* head);////单链表排序 
node *reverse(node *head);//单聊表逆置
void search_mid(node *head,node *mid);//给出一个单链表，不知道节点N的值，只遍历一次出中间节点

/*8、给定一个单向链表，设计一个时间优化并且空间优化的算法，找出该链表的倒数第m个元素。实现您的算法，注意处理相关的出错情况。m定义为当m=0时，返回链表最后一个元素。
    解析：这是一个难题，我们需要的是倒数第m个元素，所以如果我们从某个元素开始，遍历了m个元素之后刚好到达链表末尾，那么这个元素就是要找的元素。也许从链表的尾部倒推回去不是最好的办法，那么我们可以从链表头开始计数。
    思路一：我们可以先一次遍历求出链表的总长度n，然后顺序变量求出第n-m个元素，那么这个就是我们要找的元素了。
    思路二：我们用两个指针，一个当前位置指针p和一个指向第m个元素的指针q，需要确保两个指针之间相差m个元素，然后以同样的速度移动它们，如果当q到达链表末尾时，那么p指针就是指向倒数第m个元素了。
*/
node *search_last_element1(node *head,int m);//查找链表倒数第m个数值,方法一
node *search_last_element2(node *head,int m);//查找链表倒数第m个数值,方法二

node *sort(node *head)
{
	node *p;
	int n;
	int temp;

	n = length(head);
	if(head == NULL || head->next == NULL)//如果只有一个或者没有结点
	{
		return false;
	}

	p = head;
	for(int j=1; j<n; j++)
	{
		p = head;
		for(int i=0;i<n-j;i++)
		{
			if(p->data > p->next->data)//从小到大排列
			{
				temp = p->data;
				p->data = p->next->data;
				p->next->data = temp;
			}

			p = p->next;
		}
	}
	return head;
}

node *reverse(node *head)
{
	node *p1,*p2,*p3;
	if(head == NULL || head->next == NULL)
	{
		return head;
	}

	p1 = head;
	p2 = p1->next;

	while(p2)//顺序移动p1,p2,p3的位置
	{
		p3 = p2->next;
		p2->next = p1;
		p1 = p2;
		p2 = p3;
	}
	head->next = NULL;
	head = p1;//以上两步将头结点指向末尾，另一个开始

	return head;
}

void remove_head(node *head)
{
	node *p = head;
	head = head->next;
	free(p);
}

void searchmid(node *head,node *mid)
{
	node *p,*q;
	p = head;
	q = head;

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

	mid = q;
}

node *search_last_element1(node *head,int m)
{
	if(head == NULL)
	{
		return NULL;
	}

	node *p = head;
	int count = 0;
	while(p != NULL)
	{
		p = p->next;
		count++;
	}

	if(count<m)
		return NULL;

	p = head;
	for(int i=0; i<count-m; i++)
	{
		p = p->next;
	}

	return p;
}

node *search_lase_element2(node *head,int m)
{
	if(head == NULL)
		return head;

	node *p,*q;
	p = head;
	q = head;

	for(int i=0; i<m; i++)
	{
		if(p->next != NULL)
		{
			p = p->next;
		}
		else
		{
			return NULL;
		}
	}

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

	return q;
}