【摘要】链表逆转是面试环境中经常遇到的一道题目，也是我们在实际开发中可能会遇到的开发需求。和线性逆转不一样，单向链表的节点需要一个一个进行处理。有需要的朋友可以看一下，如果有没考虑周全的地方欢迎指正。
为了显示两者之间的区别，我们分别对线性内存和链表进行逆转：
（1）连续内存数据反转STATUS normal_revert(int array[], int length){int* pData ;int index = length – 1;//数组最后一个位置if(NULL == array || 0 == length)return FALSE;pData = (int*)malloc(sizeof(int) * length);assert(NULL != pData);memset(pData, 0, sizeof(int) * length);while(index >= 0){pData[length – 1 – index] = array[index];index –;}memmove(array, pData, length * sizeof(int));free(pData);//防止内存泄露pData = NULL;return TRUE;}
分析：我们看到连续内存反转函数主要做了下面几个工作： 1）分配和原来数据一样大的内存 2）从原来数据末尾开始拷贝 3）利用pData获取的数据对原来的数据进行拷贝覆盖，释放内存
（2）链表反转LNode{intdata;struct LNode *next;}LNode, *LinkedList;
① 第一种方法
/*不带头结点的链表反转*/LinkedList ReverseSinglyLinkedList(LinkedList list){LinkedList newList; //新链表第一个结点LNode*tmp;newList = (LinkedList)malloc(sizeof(LNode));newList){return NULL;}newList;//原始链表的第一个结点newList->next = NULL;){tmp next; //保存tmp->next = newList; //反转newList = tmp;next->next; /*为什么不是list = list->next,这个和while循环条件有关系*/}free(list);return newList;}
② 第二种方法
不带头结点的反转函数，该函数采用三个结构体指针分别保存 前一节点 当前节点 后一节点 的值，将当前节点的指针域值直接指向前一节点，后一节点作为链表后面的引线，再将这三个指针往后移一位，递归进行前面的动作
/*无头结点*/LinkedList reverse(LinkedList head){)) //链表为空,或只有一个结点（无需反转），直接返回return head;LNode *pre = NULL;//前一个LNode *cur = NULL;//当前LNode *ne = NULL;//后一个pre = head;//将前面几个节点的地址依次保存在新定义的结构体指针cur = head ->next;while(cur){ne = cur->next; //如果当前节点不为空，则将其指针域赋给ne指针cur->next = pre; //直接将两个指针的指向反转pre = cur;//将当前节点赋给pre，将三个指针在链表中的位子都往后移一位cur = ne;}head->next = NULL;//将原来的第一个节点的指针域赋为空，作为尾节点head = pre;//将原来的尾节点变成新链表的第一个节点return head;}
带头结点的反转函数，该函数采用三个结构体指针分别保存 前一节点 当前节点 后一节点 的值，将当前节点的指针域值直接指向前一节点，后一节点作为链表后面的引线，再将这三个指针往后移一位，递归进行前面的动作;因为此链表为带头结点的链表，头结点的数据域并没有存放有效的数据，此函数与上一函数的区别是，需要保持头结点不动，只需要反转后面存有效数据的结点部分
/*有头结点*/LinkedList reverse(LinkedList head){head;LNode *pre = NULL;//前一个LNode *cur = NULL;//当前LNode *ne = NULL;//后一个pre = head->next;//将前面几个节点的地址依次保存在新定义的结构体指针cur = pre ->next;while(cur){ne = cur->next; //如果当前节点不为空，则将其指针域赋给ne指针cur->next = pre; //直接将两个指针的指向反转pre = cur;//将当前节点赋给pre，，将三个指针在链表中的位子都往后移一位cur = ne;}head->next->next= NULL;//将原来的第一个节点的指针域赋为空，作为尾节点head->next = pre;//将原来的尾节点变成新链表的第一个节点（头结点所指向的节点）return head;}
纵然走过那么多城市，对于未知的风景，还是好奇。
