大一计算机的自学总结：单双链表的反转

前言

为了减少单个文件里的代码量（懒），于是将能用到的函数都写进一个.h文件里了。

其中大部分函数都在我“初见链表”的文章里写过了。

#include<bits/stdc++.h>

using namespace std;

typedef struct node
{
	int value;
	struct node* next;
}Node;

typedef struct nodeD
{
	int value;
	struct nodeD* last;
	struct nodeD* next;
}NodeD;

typedef struct
{
	Node* head;
	Node* tail;
}List;

typedef struct
{
	NodeD* head;
	NodeD* tail;
}ListD;

//添加链表
void add(List &list,int n)
{
	Node* p=(Node*)malloc(sizeof(Node));
	p->value=n;
	p->next=NULL;
	
	if(list.tail==NULL)
	{
		list.head=p;
		list.tail=list.head; 
	}
	else
	{
		list.tail->next=p;
		list.tail=list.tail->next;
	}
} 

//添加双链表 
void addD(ListD &listD,int n)
{
	NodeD* p=(NodeD*)malloc(sizeof(NodeD));
	p->value=n;
	p->last=p->next=NULL;
	
	if(listD.tail==NULL)
	{
		listD.head=p;
		listD.tail=listD.head;
	}
	else
	{
		p->last=listD.tail;
		listD.tail->next=p;
		listD.tail=listD.tail->next;
	}
}

//打印链表
void printList(List List)
{
	for(Node* p=List.head;p!=NULL;p=p->next)
	{
		cout<<p->value<<" ";
	}
	cout<<endl;
} 

//打印双链表
void printListD(ListD ListD)
{
	int a;
	cout<<"From head or tail?  "<<"head:0  tail:1"<<endl;
	cin>>a;
	
	if(a==0)
	{
		for(NodeD* p=ListD.head;p!=NULL;p=p->next)
		{
			cout<<p->value<<" ";
		}	
	}
	else if(a==1)
	{
		for(NodeD* p=ListD.tail;p!=NULL;p=p->last)
		{
			cout<<p->value<<" ";
		}
	}
	else
	{
		cout<<"Seriously?";
	}
	cout<<endl;
} 

//清除链表
void freeList(List &list)
{
	Node* q;
	for(Node* p=list.head;p!=NULL;p=q)
	{
		q=p->next;
		free(p);
	}
} 

//清除双链表
void freeListD(ListD &listD)
{
	NodeD* q;
	for(NodeD* p=listD.head;p!=NULL;p=q)
	{
		q=p->next;
		free(p);
	}
} 

一、双链表

#include<bits/stdc++.h>
#include"LinkedListFunction.h"
using namespace std;

int main()
{
	ListD list;
	list.head=list.tail=NULL;
	
	int n;
	cout<<"Add n to double list:"<<endl;
    do
    {
    	cout<<"n:";
        cin>>n;
        if (n != -1)
        {
            addD(list, n);
        }
    } while (n != -1);
    
    printListD(list);
	
	freeListD(list);
	return 0;
}

 双链表因为其双向连接的特性，反转输出只需选择从head开始还是从tail开始即可。

二、单链表反转

#include<bits/stdc++.h>
#include"LinkedListFunction.h"

using namespace std;

//反转链表
void Reverse(List &list)
{
	Node* lastNode=NULL;
	Node* nextNode=NULL;
	Node* t=list.head;    
	while(list.head!=list.tail)
	{
		nextNode=list.head->next;
		list.head->next=lastNode;
		lastNode=list.head;
		list.head=nextNode;
	}
	list.head->next=lastNode;
	list.tail=t;
} 

int main()
{
	List list;
	list.head=list.tail=NULL;
	
	int n;
	cout<<"Add n to list:"<<endl;
    do
    {
    	cout<<"n:";
        cin>>n;
        if (n != -1)
        {
            add(list, n);
        }
    } while (n != -1);

	cout<<"Before reverse:"<<endl;
	printList(list);
	
	Reverse(list);
	
	cout<<"After reverse:"<<endl;
	printList(list);
	
	freeList(list);
	return 0;
} 

单链表的反转就复杂得多了。反转一个单链表，不仅要将head和tail的位置互换，还要让原本指向下一个结点的next指向上一个结点。为了实现这两点，需要设置一个指向上一个结点的指针lastNode和指向下一个结点的指针nextNode。

首先，先初始化两个指针为NULL，然后先用t保存head，方便最后和tail交换。之后进入循环，即当head没有移动到tail的位置，循环继续。

循环中，为了改变每个结点next的指向，就要用到lastNode和nextNode两个指针，利用head指针，先让nextNode移动到head的下一个结点，再让head所指结点的next指针指向上一个结点，然后将lastNode移动到head的位置，最后将head移动到nextNode的位置。

跳出循环后，即head移动到了tail的位置，此时需要注意，head(tail)所指结点的next还没有被改变，即仍然指向NULL，所以需要让此时head所指结点的next指向lastNode，最后让tail去到最初head的位置即可。

总结

相比双链表，单链表的反转复杂得多，重点是反转时借助的lastNode和nextNode两个指针。

END