反转链表

//头插法反转
ListNode* reverseList(ListNode* head) 
{
    ListNode dummyHead;
    dummyHead.next = NULL;
    ListNode* tmp;
    while(head)
    {
        tmp = head->next;
        head->next = dummyHead.next;//容易忽略
        dummyHead.next = head;
        head = tmp;
    }
    return dummyHead.next;
}

判断回文链表

bool isPalindrome(ListNode* head)
{
	ListNode* fast = head;
	ListNode* slow = head;
	while(fast&&fast->next)//快慢指针找到中间节点和尾节点
	{
	    fast = fast->next->next;
	    slow = slow->next;
	}
	if(fast!=NULL) //区分奇数个和偶数个的情况
	    slow = slow->next;
	//反转后半部分链表
	ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
	dummy->next = NULL;
	ListNode* tmp;
	while(slow)
	{
	    tmp = slow->next;
	    slow->next = dummy->next;
	    dummy->next = slow;
	    slow = tmp;
	}
	tmp = dummy->next;
	while(tmp)
	{
	    if(head->val != tmp->val)
	        return false;
	    tmp = tmp->next;
	    head = head->next;
	}
	return true;
}

递归版本：

ListNode* front;
bool process(ListNode* cur)
{
    if(!cur)
        return true;
    if(process(cur->next) && (front->val == cur->val))
    {
        front = front->next;
        return true;
    }
    else
        return false;
}
bool isPalindrome(ListNode* head) 
{
    front = head;
    return process(head);
}

二分查找

#include <iostream>
using namespace std;

// 递归版本的二分查找
int binarySearchRecursive(int arr[], int left, int right, int target) 
{
    if (left > right) //注意没有取等
	    return -1;
    int mid = (right + left) / 2;
    if (arr[mid] == target) 
        return mid; 
    if (target < arr[mid]) 
        return binarySearchRecursive(arr, left, mid - 1, target);
    else 
        return binarySearchRecursive(arr, mid + 1, right, target);
}

#include <iostream>
using namespace std;

// 非递归版本的二分查找
int binarySearchIterative(int arr[], int n, int target) {
    int left = 0; 
    int right = n - 1; 
    while (left <= right) //注意取等
    {
        int mid = (right + left) / 2; // 计算中间索引
        if (arr[mid] == target) 
            return mid; 
        if (target < arr[mid]) 
            right = mid - 1; 
        else 
            left = mid + 1; // 在右半部分查找
    }
    return -1; // 如果没有找到目标值，返回 -1
}

寻找众数

int Majority(int A[], int n)
{
    //寻找众数
    int c,count=1;
    c=A[0];
    for(int i=1;i<n;i++)
    {
        if(A[i]==c)
            count++;
        else
        {
            if(count>0)
                count--;
            else
            {
                c=A[i];
                count=1;
            }
        }
    }
    return c;
}