反转单向链表

嗯,首先,说一件小事,昨天还在犹豫盒子支付还是海泰康,今天盒子支付经理给我回电话了,说他们也同样能达到海泰康给出的薪资。确实挺欣慰的。能力能够得到公司的认可,说明在深圳,真的是凭能力说话。话说昨天的一道笔试题,用c++实现单项链表的反转链表。我已经快3年没有写过c++了,写的一塌糊涂,不是思想不会而是语法几乎忘记了。
想到这个问题,我立马想到的一个思路就是遍历链表,用一个指针指向最尾节点,然后重新遍历,从第一个节点开始,将每一个节点插入最后一个节点末位。
步骤如下:
12345
23451
34521
45321
54321
今天没事实现了下(写了这么久的java,忽然转到写c++很不习惯,呵呵)

#include<iostream>
#include<set>
using
	namespace std;
struct	node{
	int data;
	 node *next;
};

//找到最后一个节点
node* findlast(node *head){
	while(head->next){
		head=head->next;
	}
	return	head;

}
//把目标结点插入到最后一个节点后面
void insert(node *aim,node * last){
	if(aim==NULL){return;}
	if(NULL==last->next){
		last->next=aim;
		aim->next=NULL;
	}else{
		node *temp=last->next;
		last->next=aim;
		aim->next=temp;
	}
}

//反转函数
void reverse(node *head){
	node *last=findlast(head);
	while(head!=last){
		node *temp=head->next;
		insert(head,last);
		head=temp;
	}
	cout<<head->data;
}

int main(){
	node *nd=NULL,*head=NULL;	
	for(int i=0;i<5;i++)
	{
		node *temp=(node *)malloc(sizeof(node));
		temp->data=i;
		temp->next=NULL;
		if(NULL!=nd){
		   nd->next=temp;
		   nd=temp;
		} else{
		   head=nd=temp;
		}	 
 	}

	reverse(head);
	system("pause");
return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *