算法总结

1.链表是否有环

struct Node
{
     int iData;
     Node* pNext;
}

bool IsLoop(Node* pHead)
{
     Node* pSlow = pHead;
     Node* pFast = pHead;
     while((NULL!=pFast)&&(NULL!=pFast->pNext))
     {
         pSlow = pSlow->pNext;
         pFast = pFast->pNext->pNext;
         if(pSlow==pFast)
         return true;
     }
     return false;
}

2.链表逆序

递归:

Node* reverseList(Node* pHead)
{
     if((NULL==pHead)||(NULL==pHead->pNext))
         return pHead;

    Node* pNewHead = reverseList(pHead->pNext);
     pHead->pNext->pNext = pHead;
     pHead->pNext = NULL;
     return pNewHead;
}

3.冒泡排序

void bubble_sort(int data[],size_t size){//冒泡

int i,j;

for(i=0;i<size-1;i++){

int order = 1;//设置是否交换的变量,如果交换=0

for(j=0;j<size-1-i;j++){

if(data[j] > data[j+1]){//如果前面比后面大

int temp = data[j];//交换

data[j] = data[j+1];

data[j+1] = temp;

order = 0; //交换 置0

}

}

if(order) break;

}

}

4.快速排序

int Partition(int a[], int low, int high)

{

int x = a[high];//将输入数组的最后一个数作为主元,用它来对数组进行划分

int i = low - 1;//i是最后一个小于主元的数的下标

for (int j = low; j < high; j++)//遍历下标由low到high-1的数 {

if (a[j] < x)//如果数小于主元的话就将i向前挪动一个位置,并且交换j和i所分别指向的数 {

int temp;

i++;

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

//经历上面的循环之后下标为从low到i(包括i)的数就均为小于x的数了,现在将主元和i+1位置上面的数进行交换

a[high] = a[i + 1];

a[i + 1] = x;

return i + 1;

}

void QuickSort(int a[], int low, int high)

{

if (low < high)

{

int q = Partition(a, low, high);

QuickSort(a, low, q - 1);

QuickSort(a, q + 1, high);

}

}

上一篇:剑指offer6:从尾到头打印链表


下一篇:链表中环的入口结点