nowcoder 左神算法1-白红宇

nowcoder 左神算法1

阅读量：3881 次

发布时间：2019-05-23

本文共 20128 字，大约阅读时间需要 67 分钟。

归并

归并的核心思想是先让序列的左半部分有序、再让序列的右半部分有序，最后从两个子序列（左右两半）从头开始逐次比较，往辅助序列中填较小的数。

以序列{2,1,4,3}为例，归并的过程大致如下：

代码示例：

void merge(int arr[],int helpArr[], int startIndex, int midIndex,int endIndex) {

int L = startIndex, R = midIndex + 1, i = startIndex;

while (L <= midIndex && R <= endIndex) { //只要没有指针没越界就逐次比较

helpArr[i++] = arr[L] < arr[R] ? arr[L++] : arr[R++];

}

while (L != midIndex + 1) {

helpArr[i++] = arr[L++];

}

while (R != endIndex + 1) {

helpArr[i++] = arr[R++];

}

for (i = startIndex; i <= endIndex; i++) {

arr[i] = helpArr[i];

}

void mergeSort(int arr[],int helpArr[], int startIndex, int endIndex) {

int midIndex;

if (startIndex < endIndex) { //当子序列只含一个元素时，不再进行此子过程

//(endIndex+startIndex)/2可能会导致int溢出，下面求中位数的做法更安全

midIndex = startIndex + ((endIndex - startIndex) >> 1);

mergeSort(arr, helpArr, startIndex, midIndex); //对左半部分排序

mergeSort(arr, helpArr, midIndex + 1, endIndex); //对右半部分排序

merge(arr, helpArr, startIndex, midIndex, endIndex); //使整体有序

}

int main(){

int arr[] = {

9, 1, 3, 4, 7, 6, 5};

travels(arr, 7);//遍历打印

int helpArr[7];

mergeSort(arr, helpArr, 0, 7);

travels(arr, 7);

return 0;

}

此的核心就是第24、25、26这三行。第26行应该不难理解，就是使用两个指针L、R外加一个辅助数组，将两个序列有序地并入辅助数组。但为什么24、25行执行过后数组左右两半部分就分别有序了呢？这就又牵扯到了归并的核心思想：先让一个序列左右两半部分有序，然后再并入使整体有序。因此24、25是对左右两半部分分别递归执行归并，直到某次递归时左右两半部分均为一个元素时递归终止。当一个序列只含两个元素时，调用mergeSort会发现24、25行是无效操作，直接执行merge。就像上图所示，两行递归完毕后，左右两半部分都会变得有序。

当一个递归过程比较复杂时（不像递归求阶乘那样一幕了然），我们可以列举简短样本进行分析。

对于这样复杂的递归行为，千万不要想着追溯整个递归过程，只需分析第一步要做的事（比如此例中第一步要做的是就是mergeSort函数所呈现出来的那样：对左半部分、对右半部分、最后并入，你先不管是怎么的，不要被24、25行的mergeSort给带进去了）和递归终止的条件（比如此例中是`startIndex>=endIndex，即要的序列只有一个元素时）。

归并的时间复杂度是O(nlogn)，额外空间复杂度是O(n)。

根据Master公式（本文 小技巧一节中有讲到）可得T(n)=2T(n/2)+O(n)，第一个2的含义是子过程（对子序列进行归并）要执行两次，第二个2的含义是子过程样本量占一半（因为分成了左右两半部分），最后O(n)表示左右有序之后进行的并入操作为O(n+n)=O(n)(L、R指针移动次数总和为n，将辅助数组覆盖源数组为n)，符合T(n)=aT(n/b)+O(n^d)，经计算该的时间复杂度为O(nlogn)

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例如：

对于数组[1,3,4,2,5]

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

简单的做法就是遍历一遍数组，将当前遍历的数与该数之前数比较并记录小于该数的数。易知其时间复杂度为O(n^2)（0+1+2+……+n-1）。

更优化的做法是利用归并的并入逻辑：

对应代码：

int merge(int arr[],int helpArr[], int startIndex, int midIndex,int endIndex) {

int L = startIndex, R = midIndex + 1, i = startIndex;

int res=0;

while (L <= midIndex && R <= endIndex ) { //只要没有指针没越界就逐次比较

res += arr[L] < arr[R] ? arr[L] * (endIndex - R + 1) : 0;

helpArr[i++] = arr[L] < arr[R] ? arr[L++] : arr[R++];

}

while (L != midIndex + 1) {

helpArr[i++] = arr[L++];

}

while (R != endIndex + 1) {

helpArr[i++] = arr[R++];

}

for (i = startIndex; i <= endIndex; i++) {

arr[i] = helpArr[i];

}

return res;

}

int mergeSort(int arr[],int helpArr[], int startIndex, int endIndex) {

int midIndex;

if (startIndex < endIndex) { //当子序列只含一个元素时，不再进行此子过程

midIndex = startIndex + ((endIndex - startIndex) >> 1);

return mergeSort(arr, helpArr, startIndex, midIndex) + //对左半部分排序

mergeSort(arr, helpArr, midIndex + 1, endIndex) + //对右半部分排序

merge(arr, helpArr, startIndex, midIndex, endIndex); //使整体有序

}

return 0; //一个元素时不存在小和

}

int main(){

int arr[] = {

1,3,4,2,5};

int helpArr[5];

printf("small_sum:%d\n",mergeSort(arr, helpArr, 0, 4)) ;

return 0;

}

该在归并的基础上做了略微改动，即merge中添加了变量res记录每次并入操作应该累加的小和、mergeSort则将每次并入应该累加的小和汇总。此种做法的复杂度与归并的相同，优于遍历的做法。可以理解，依次求每个数的小和过程中有很多比较是重复的，而利用归并求小和时利用了并入的两个序列分别有序的特性省去了不必要的比较，如134并入25时，2>1直接推出2后面的数都>1，因此直接1*(endIndex-indexOf(2)+1)即可。这在样本量不大的情况下看不出来优化的效果，试想一下如果样本量为2^32，那么依照前者求小和O(n^2)可知时间复杂度为O(21亿的平方)，而归并求小和则只需O(21亿*32)，足以见得O(n^2)和O(nlogn)的优劣。

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。

这题的思路也可以利用归并来解决，在并入操作时记录arr[L]>arr[R]的情况即可。

int* partition(int arr[], int startIndex, int endIndex){ ;

int small = startIndex - 1, great = endIndex + 1, i = startIndex;

while (i <= great - 1) {

if (arr[i] < arr[endIndex]) {

swap(arr[++small], arr[i++]);

} else if (arr[i] > arr[endIndex]){

swap(arr[--great], arr[i]);

} else {

i++;

}

int range[] = {small, great};

return range;

}

void quickSort(int arr[], int startIndex, int endIndex) {

if (startIndex > endIndex) {

return;

}

int* range = partition(arr, startIndex, endIndex);

quickSort(arr, startIndex, range[0]);

quickSort(arr, range[1], endIndex);

}

int main(){

int arr[] = {

1, 5, 6, 2, 7, 3, 8, 0};

travles(arr, 8); //1 5 6 2 7 3 8 0

quickSort(arr, 0,7);

travles(arr, 8); //0 1 2 3 5 6 7 8

return 0;

}

比较一下经典和使用荷兰国旗问题改进后的经典，不难发现，后者一次partition能去除一个以上的元素（等于arr[endIndex]的区域），而前者每次partition只能去除一个元素，这里的去除相当于安排（）好了对应元素的位置。因此后者比经典更优，但是优化不大，只是常数时间内的优化，实质上的效率还是要看数据状况（最后的情况为O(nlogn)，最坏的情况为O(n^2)）。

随机快排——O(nlogn)

上面谈到了快排的短板是依赖数据状况，那么我们有没有办法消除这个依赖，让他成为真正的O(nlogn)呢？

事实上，为了让中的操作不依托于数据状况（如快排中每一次partition取尾元素作为比较，这就没有规避样本的数据状况，如果尾元素是最大或最小值就成了最坏情况）常常有两种做法：

1、使用随机取数

2、将样本数据哈希打乱

随机快排就是采用上了上述第一种解决方案，在每一轮的partition中随机选择序列中的一个数作为要比较的数：

#include

void swap(int &a, int &b){

int temp = a;

a = b;

b = temp;

}

//产生[startIndex,endIndex]之间的随机整数

int randomInRange(int startIndex,int endIndex){

return rand() % (endIndex - startIndex + 1) + startIndex;

}

int* partition(int arr[], int startIndex, int endIndex){ ;

int small = startIndex - 1, great = endIndex + 1, i = startIndex;

int randomNum = arr[randomInRange(startIndex, endIndex)];

while (i <= great - 1) {

if (arr[i] < randomNum) {

swap(arr[++small], arr[i++]);

} else if (arr[i] > randomNum){

swap(arr[--great], arr[i]);

} else {

i++;

}

int range[] = {small, great};

return range;

}

void quickSort(int arr[], int startIndex, int endIndex) {

if (startIndex > endIndex) {

return;

}

int* range = partition(arr, startIndex, endIndex);

quickSort(arr, startIndex, range[0]);

quickSort(arr, range[1], endIndex);

}

void travles(int dataArr[], int length){

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

printf("%d ", dataArr[i]);

}

printf("\n");

}

int main(){

srand(time(NULL));//此后调用rand()时将以调用时的时间为随机数种子

int arr[] = {

9,7,1,3,2,6,8,4,5};

travles(arr, 9);

quickSort(arr, 0,8);

travles(arr, 9);

return 0;

}

观察比较代码可以发现随机快排只不过是在partition时随机选出一个下标上的数作为比较对象，从而避免了每一轮选择尾元素会受数据状况的影响的问题。

那么随机快排的时间复杂度又为多少呢？

经数学论证，由于每一轮partition选出的作为比较对象的数是随机的，即序列中的每个数都有1/n的概率被选上，那么该时间复杂度为概率事件，经数学论证该的数学期望为O(nlogn)。虽然说是数学期望，但在实际工程中，常常就把随机快排的时间复杂度当做O(nlog)。

堆

什么是堆

堆结构就是将一颗完全映射到数组中的一种存储方式：

大根堆和小根堆

当堆的每一颗子树（包括树本身）的最大值就是其结点时称为大根堆；相反，当堆的每一颗子树的最小值就是其根结点时称为小根堆。其中大根堆的应用较为广泛，是一种很重要的数据结构。

heapInsert和heapify

大根堆最重要的两个操作就是heapInsert和heapify，前者是当一个元素加入到大根堆时应该自底向上与其父结点比较，若大于父结点则交换；后者是当堆中某个结点的数值发生变化时，应不断向下与其孩子结点中的最大值比较，若小于则交换。下面是对应的代码：

//index之前的序列符合大根堆排序，将index位置的元素加入堆结构，但不能破坏大根堆的特性

void heapInsert(int arr[],int index){

while (arr[index] > arr[(index - 1) / 2]) { //当该结点大于父结点时

swap(arr[index], arr[(index - 1) / 2]);

index = (index - 1) / 2; //继续向上比较

}

//数组中下标从0到heapSize符合大根堆排序

//index位置的值发生了变化，重新调整堆结构为大根堆

//heapSize指的是数组中符合大根堆排序的范围而不是数组长度,最大为数组长度，最小为0

void heapify(int arr[], int heapSize, int index){

int leftChild = index * 2 + 1;

while (leftChild < heapSize) { //当该结点有左孩子时

int greatOne = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ?

leftChild + 1 : leftChild; //只有当右孩子存在且大于左孩子时，最大值是右孩子，否则是左孩子

greatOne = arr[greatOne] > arr[index] ? greatOne : index;//将父结点与最大孩子结点比较，确定最大值

if (greatOne == index) {

//如果最大值是本身，则不用继续向下比较

break;

}

swap(arr[index], arr[greatOne]);

//next turn下一轮

index = greatOne;

leftChild = index * 2 + 1;

}

建立大根堆

void buildBigRootHeap(int arr[],int length){

if (arr == NULL || length <= 1) {

return;

}

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

heapInsert(arr, i);

}

利用heapify

前面做了那么多铺垫都是为了建立大根堆，那么如何利用它来呢？

对应代码实现如下：

void heapSort(int arr[],int length){

if (arr == NULL || length <= 1) {

return;

}

//先建立大根堆

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

heapInsert(arr, i);

}

//循环弹出堆顶元素并heapify

int heapSize = length;

swap(arr[0], arr[--heapSize]);//相当于弹出堆顶元素

while (heapSize > 0) {

heapify(arr, heapSize, 0);

swap(arr[0], arr[--heapSize]);

}

int main(){

int arr[] = {

9,7,1,3,6,8,4,2,5};

heapSort(arr, 9);

travles(arr, 9);

return 0;

}

堆的优势在于无论是入堆一个元素heapInsert还是出堆一个元素之后的heapify都不是将整个样本遍历一遍（O(n)级别的操作），而是树层次上的遍历（O(logn)级别的操作）。

这样的话堆过程中，建立堆的时间复杂度为O(nlogn)，循环弹出堆顶元素并heapify的时间复杂度为O(nlogn)，整个堆的时间复杂度为O(nlogn)，额外空间复杂度为O(1)

优先级队列结构（比如Java中的PriorityQueue）就是堆结构。

的稳定性

的稳定性指的是前后是否维持值相同的元素在序列中的相对次序。如序列271532，在过程中如果能维持第一次出现的2在第二次出现的2的前面，那么该能够保证稳定性。首先我们来分析一下前面所讲的稳定性，再来谈谈稳定性的意义。

冒泡。可以保证稳定性，只需在比较相邻两个数时只在后一个数比前一个数大的情况下才交换位置即可。

选择。无法保证稳定性，比如序列926532，在第一轮maxIndex的选择出来之后（maxIndex=0），第二次出现的2（尾元素）将与9交换位置，那么两个2的相对次序就发生了变化，而这个交换是否会影响稳定性在我们coding的时候是不可预测的。

插入。可以保证稳定性，每次插入一个数到有序序列中时，遇到比它大的就替换，否则不替换。这样的话，值相同的元素，后面插入的就总在前面插入的后面了。

归并。可以保证稳定性，在左右两半子序列排好序后的merge过程中，比较大小时如果相等，那么优先插入左子序列中的数。

快排。不能保证稳定性，因为partition的过程会将比num小的与small区域的右一个数交换位置，将比num大的与great区域的左一个数交换位置，而small、great分居序列两侧，很容易打乱值相同元素的相对次序。

堆。不能保证稳定性。如果交换位置的结点是相邻层次的可以保证稳定性，但堆中弹出堆顶元素后的heapify交换的是第一层的结点和最后一层的结点。

维持稳定性一般是为了满足业务需求。假设下面是一张不同厂商下同一款产品的价格和情况表：

品牌	价格	销量
	1603	92
	1603	74
	1604	92

要求先按价格，再按销量。如果保证稳定性，那么后应该是这样的：

品牌	价格	销量
	1603	92
	1604	92
	1603	74

即按销量后，销量相同的两条记录会保持之前的按价格的状态，这样先前的价格这个工作就没白做。

比较器的使用

之前所讲的一些大都是对基本类型的，但实际工程中要的对象可能是无法预测的，那么如何实现一个通用的以应对呢？事实上，之前的都可以归类为基于比较的。也就是说我们只需要对要比较的对象实现一个比较器，然后基于比较器来，这样和具体要的对象之间就解耦了。以后在之前，基于要的对象实现一个比较器（定义了如何比较对象大小的逻辑），然后将比较器丢给即可，这样就实现了复用。

在Java（本人学的是Java方向）中，这个比较器就是Comparator接口，我们需要实现其中的compare方法，对于要的对象集合定义一个比较大小的逻辑，然后在构造用来添加这类对象的有序容器时传入这个构造器即可。封装好的容器会在容器元素发生改变时使用我们的比较器来重新组织这些元素。

import lombok.AllArgsConstructor;

import lombok.Data;

import java.util.PriorityQueue;

import java.util.Comparator;

public class ComparatorTest {

static class Student {

private long id;

private String name;

private double score;

}

static class IdAscendingComparator implements Comparator {

/**

* 底层排序算法对两个元素比较时会调用这个方法

* @param o1

* @param o2

*

*/

return o1.getId() < o2.getId() ? -1 : 1;

}

public static void main(String[] args) {

//大根堆

PriorityQueue heap = new PriorityQueue(new IdAscendingComparator());

Student zhangsan = new Student(1000, "zhangsan", 50);

Student lisi = new Student(999, "lisi", 60);

Student wangwu = new Student(1001, "wangwu", 50);

heap.add(zhangsan);

heap.add(lisi);

heap.add(wangwu);

while (!heap.isEmpty()) {

System.out.println(heap.poll());//弹出并返回堆顶元素

}

还有TreeSet等，都是在构造是传入比较器，否则将直接根据元素的值（Java中引用类型变量的值为地址，比较将毫无意义）来比较，这里就不一一列举了。

有关问题的补充

归并可以做到额外空间复杂度为O(1)，但是比较难，感兴趣的可以搜 归并内部缓存法

快速可以做到保证稳定性，但是很难，可以搜01 stable sort（论文）

有一道题是：是奇数放到数组左边，是偶数放到数组右边，还要求奇数和奇数之间、偶数和偶数之间的原始相对次序不变。这道题和归并如出一辙，只不过归并是将arr[length-1]或arr[randomIndex]作为比较的标准，而这道题是将是否能整除2作为比较的标准，这类问题都同称为o1 sort，要使这类问题做到稳定性，要看01 stable sort这篇论文。

工程中的综合

实际工程中的一般会将归并、插入、快速综合起来，集大家之所长来应对不同的场景要求：

当要的元素为基本数据类型且元素个数较少时，直接使用插入。因为在样本规模较小时（比如60），O(NlogN)的优势并不明显甚至不及O(N^2)，而在O(N^2)的中，插入的常数时间操作最少。

当要的元素为对象数据类型（包含若干字段），为保证稳定性将采用归并。

当要的元素为基本数据类型且样本规模较大时，将采用快速。

桶

上一节中所讲的都是基于比较的，也即通过比较确定每个元素所处的位置。那么能不能不比较而实现呢？这就涉及到了桶这个方法论：准备一些桶，将序列中的元素按某些规则放入翻入对应的桶中，最后根据既定的规则依次倒出桶中的元素。

非基于比较的，与被的样本的实际数据状况有很大关系，所以在实际中并不常用。

计数

计数是桶方法论的一种实现，即准备一个与序列中元素的数据范围大小相同的数组，然后遍历序列，将遇到的元素作为数组的下标并将该位置上的数加1。例如某序列元素值在0~100之间，请设计一个对其，要求时间复杂度为O(N)。

#include

void countSort(int arr[],int length){

int bucketArr[101];

int i;

for(i = 0 ; i <= 100 ; i++){

bucketArr[i]=0; //init buckets

}

for(i = 0 ; i < length ; i++){

bucketArr[arr[i]]++; //put into buckets

}

int count, j=0;

for(i = 0 ; i <= 100 ; i++) {

if (bucketArr[i] != 0) { //pour out

count = bucketArr[i];

while (count-- > 0) {

arr[j++] = i;

}

void travels(int arr[], int length){

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

printf("%d ", arr[i]);

}

printf("\n");

}

int main(){

int arr[] = {

9, 2, 1, 4, 5, 2, 1, 6, 3, 8, 1, 2};

travels(arr, 12);//9 2 1 4 5 2 1 6 3 8 1 2

countSort(arr, 12);

travels(arr, 12);//1 1 1 2 2 2 3 4 5 6 8 9

return 0;

}

如果下次面试官问你有没有事件复杂度比O(N)更优的时，不要忘了计数哦！！！

补充问题

给定一个数组，求如果后，相邻两数的最大值，要求时间复杂度为O(N)，且要求不能用非基于比较的。

这道题的思路比较巧妙：首先为这N个数准备N+1个桶，然后以其中的最小值和最大值为边界将数值范围均分成N等分，然后遍历数组将对应范围类的数放入对应的桶中，下图以数组长度为9举例

这里比较难理解的是：

题目问的是求如果后，相邻两数的最大差值。该巧妙的借助一个空桶（N个数进N+1个桶，必然有一个是空桶），将问题转向了求两个相邻非空桶
（其中可能隔着若干个空桶）之间前桶的最大值和后桶最小值的差值，而无需在意每个桶中进了哪些数（只需记录每个桶入数的最大值和最小值以及是否有数）

对应代码如下：

#include

//根据要入桶的数和最大最小值得到对应桶编号

int getBucketId(int num,int bucketsNum,int min,int max){

return (num - min) * bucketsNum / (max - min);

}

int max(int a, int b){

return a > b ? a : b;

}

int min(int a, int b){

return a < b ? a : b;

}

int getMaxGap(int arr[], int length) {

if (arr == NULL || length < 2) {

return -1;

}

int maxValue = -999999, minValue = 999999;

int i;

//找出最大最小值

for (i = 0; i < length; ++i) {

maxValue = max(maxValue, arr[i]);

minValue = min(minValue, arr[i]);

}

//记录每个桶的最大最小值以及是否有数，初始时每个桶都没数

int maxs[length + 1], mins[length + 1];

bool hasNum[length + 1];

for (i = 0; i < length + 1; i++) {

hasNum[i] = false;

}

//put maxValue into the last bucket

mins[length] = maxs[length] = maxValue;

hasNum[length] = true;

//iterate the arr

int bid; //bucket id

for (i = 0; i < length; i++) {

if (arr[i] != maxValue) {

bid = getBucketId(arr[i], length + 1, minValue, maxValue);

//如果桶里没数，则该数入桶后，最大最小值都是它，否则更新最大最小值

mins[bid] = !hasNum[bid] ? arr[i] : arr[i] < mins[bid] ? arr[i] : mins[bid];

maxs[bid] = !hasNum[bid] ? arr[i] : arr[i] > maxs[bid] ? arr[i] : maxs[bid];

hasNum[bid] = true;

}

//find the max gap between two nonEmpty buckets

int res = 0, j = 0;

for (i = 0; i < length; ++i) {

j = i + 1;//the next nonEmtpy bucket id

while (!hasNum[j]) {

//the last bucket must has number

j++;

}

res = max(res, (mins[j] - maxs[i]));

}

return res;

}

int main(){

int arr[] = {

13, 41, 67, 26, 55, 99, 2, 82, 39, 100};

printf("%d", getMaxGap(arr, 9)); //17

return 0;

}

反转单和双向

实现反转单向和反转双向的函数，要求时间复杂度为O(N)，额外空间复杂度为O(1)

此题的难点就是反转一个结点的next指针后，就无法在该结点通过next指针找到后续的结点了。因此每次反转之前需要将该结点的后继结点记录下来。

#include

#define MAX_SIZE 100

struct LinkNode{

int data;

LinkNode* next;

};

void init(LinkNode* &head){

head = (LinkNode*)malloc(sizeof(LinkNode));

head->next=NULL;

}

void add(int i,LinkNode* head){

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

p->data = i;

p->next = head->next;

head->next = p;

}

void printList(LinkNode* head){

if(head==NULL)

return;

LinkNode* p = head->next;

while(p != NULL){

printf("%d ",p->data);

p = p->next;

}

printf("\n");

}

#include

#include "LinkList.cpp"

void reverseList(LinkNode *head){

if(head == NULL)

return;

LinkNode* cur = head->next;

LinkNode* pre = NULL;

LinkNode* next = NULL;

while(cur != NULL){

next = cur->next;

cur->next = pre;

pre = cur;

cur = next;

}

//pre -> end node

head->next = pre;

return;

}

int main(){

LinkNode* head;

init(head);

add(1,head);

add(2,head);

add(3,head);

add(4,head);

printList(head);

reverseList(head);

printList(head);

}

请实现一个函数判断某个单是否是回文结构，如1->3->1返回true、1->2->2->1返回true、2->3->1返回false。

我们可以利用回文前后两半部分逆序的特点、结合栈先进后出来求解此问题。将中间结点之前的结点依次压栈，然后从中间结点的后继结点开始遍历的后半部分，将遍历的结点与栈弹出的结点比较。

代码示例如下：

#include

#include "LinkList.cpp"

#include "SqStack.cpp"

/*

判断某链表是否是回文结构

1、首先找到链表的中间结点（若是偶数个结点则是中间位置的左边一个结点）

2、使用一个栈将中间结点之前的结点压栈，然后从中间结点的后一个结点开始从栈中拿出结点比较

*/

bool isPalindromeList(LinkNode* head){

if(head == NULL)

return false;

LinkNode *slow = head , *fast = head;

SqStack* stack;

init(stack);

//fast指针每走两步，slow指针才走一步

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

fast = fast->next->next;

slow = slow->next;

push(slow,stack);

}

//链表没有结点或只有一个结点，不是回文结构

if(isEmpty(stack))

return false;

//判断偶数个结点还是奇数个结点

if(fast->next != NULL){ //奇数个结点,slow需要再走一步

slow = slow->next;

}

//从slow的后继结点开始遍历链表，将每个结点与栈顶结点比较

LinkNode* node;

slow = slow->next;

while(slow != NULL){

pop(stack,node);

//一旦发现有一个结点不同就不是回文结构

if(slow->data != node->data)

return false;

slow = slow->next;

}

return true;

}

int main(){

LinkNode* head;

init(head);

add(2,head);

add(3,head);

add(2,head);

printList(head);

if(isPalindromeList(head)){

printf("是回文链表");

}else{

printf("不是回文链表");

}

return 0;

}

LinkList.cpp:

#include

#define MAX_SIZE 100

struct LinkNode{

int data;

LinkNode* next;

};

void init(LinkNode* &head){

head = (LinkNode*)malloc(sizeof(LinkNode));

head->next=NULL;

}

void add(int i,LinkNode* head){

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

p->data = i;

p->next = head->next;

head->next = p;

}

void printList(LinkNode* head){

if(head==NULL)

return;

LinkNode* p = head->next;

while(p != NULL){

printf("%d ",p->data);

p = p->next;

}

printf("\n");

}

SqStack:

#include

struct SqStack{

LinkNode* data[MAX_SIZE];

int length;

};

void init(SqStack* &stack){

stack = (SqStack*)malloc(sizeof(SqStack));

stack->length=0;

}

bool isEmpty(SqStack* stack){

if(stack->length > 0)

return false;

return true;

}

bool isFull(SqStack* stack){

if(stack->length == MAX_SIZE)

return true;

return false;

}

void push(LinkNode* i,SqStack* stack){

if(stack==NULL)

return;

if(!isFull(stack)){

stack->data[stack->length++] = i;

}

bool pop(SqStack* stack,LinkNode* &i){

if(stack==NULL)

return false;

if(!isEmpty(stack))

i = stack->data[--stack->length];

return true;

}

进阶：要求使用时间复杂度为O(N)，额外空间复杂度为O(1)求解此问题。

思路：我们可以先将的后半部分结点的next指针反向，然后从的两头向中间推进，逐次比较。（当然了，为了不破坏原始数据结构，我们在得出结论之后还需要将指针恢复原样）

100

101

102

103

104

105

106

107

108

109

110

111

#include

#include "LinkList.cpp"

#include "SqStack.cpp"

bool isPalindromeList(LinkNode* head){

/*第一步、与方法一一样，找到中间结点*/

if(head == NULL)

return false;

LinkNode *n1 = head , *n2 = head;

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

n2 = n2->next->next;

n1 = n1->next;

}

//如果没有结点或者只有一个首结点

if(n2 == head){

return false;

}

//如果是奇数个结点

if(n2->next != NULL){

n1 = n1->next; //n1 -> middle node

}

/*第二步、不使用额外空间，在链表自身上做文章：反转链表后半部分结点的next指针*/

n2 = n1->next; // n2 -> right part first node

n1->next = NULL;//middle node->next = NULL

LinkNode *n3 = NULL;

while (n2 != NULL) {

n3 = n2->next; //记录下一个要反转指针的结点

n2->next = n1; //反转指针

n1 = n2;

n2 = n3;

}

//n1 -> end node

n3 = n1; //record end node

n2 = head->next;

while (n2 != NULL) {

if (n2->data != n1->data) {

return false;

}

n2 = n2->next; //move n2 forward right

n1 = n1->next; //move n1 forward left

}

//recover the right part nodes

n2 = n3; //n2 -> end node

n1 = NULL;

while (n2 != NULL) {

n3 = n2->next;

n2->next = n1;

n1=n2;

n2 = n3;

}

return true;

}

/*bool isPalindromeList(LinkNode* head){

if(head == NULL)

return false;

LinkNode *slow = head , *fast = head;

SqStack* stack;

init(stack);

//fast指针每走两步，slow指针才走一步

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

fast = fast->next->next;

slow = slow->next;

push(slow,stack);

}

//链表没有结点或只有一个结点，不是回文结构

if(isEmpty(stack))

return false;

//判断偶数个结点还是奇数个结点

if(fast->next != NULL){ //奇数个结点,slow需要再走一步

slow = slow->next;

}

//从slow的后继结点开始遍历链表，将每个结点与栈顶结点比较

LinkNode* node;

slow = slow->next;

while(slow != NULL){

pop(stack,node);

//一旦发现有一个结点不同就不是回文结构

if(slow->data != node->data)

return false;

slow = slow->next;

}

return true;

}*/

int main(){

LinkNode* head;

init(head);

add(2,head);

add(3,head);

add(1,head);

printList(head);

if(isPalindromeList(head)){

printf("yes");

}else{

printf("no");

}

return 0;

}

转载地址：http://uzzhn.baihongyu.com/

你可能感兴趣的文章

数据库SQL语言语法总结7---嵌入式SQL

查看>>

数据库SQL语言语法总结1---表操作

查看>>

Numpy中stack()，hstack()，vstack()函数详解

ESC ubuntu16.04 ipv6配置

查看>>

visual studio 创建 C/C++静态库和动态库