第25题：K个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

思路
1.当k = 1的时候，链表不用翻转；
2.对每k个结点组成的子链进行翻转，然后将翻转的子链头尾接入链表。（注意，对于第一个k个结点的子链，翻转后不存在前驱结点）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *s;
    if(!head) return NULL;
    if(!head->next) return head;
    struct ListNode * new = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return new;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode  *cur ,* pre, *dos;
    if(k == 1) return head;
    cur = head;
    pre = head;
    int num = k;
    while(num)
    {
        if(!cur)  return head;
        if(num == 1)  dos = cur;
        cur = cur->next;
        num--;
    }
    dos->next = NULL;
    head =  reverseList(head);
    pre->next = cur;
    while(cur)
    {
        num = k;
        while(num)
        {
            if(!cur)  return head;
            if(num == 1)  dos = cur;
            cur = cur->next;
            num--;
        }
        dos->next = NULL;
        dos = pre->next;
        pre->next = reverseList(pre->next);
       dos->next = cur;
       pre = dos;
        
    }
    return head;
}

第29题：两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers

思路
初一看这题，第一想法是将除数和被除数取绝对值，然后重复步骤都用被除数减去除数，然后result（结果）加1，直到结果小于除数。这个想法正确，但是时间太长了。
那么怎么缩短时间呢？
我们知道int型数据可以写成32位二进制数，也就是说一个int型的数据可以表示成2^i（i= 1,2，……，31）的和，所以我们可以得到下面的函数。

#define INT_MAX 0X7FFFFFFF
#define INT_MIN 0X80000000

int divide(int dividend, int divisor)
{
    int result = 0;    
    if(dividend == 0)   
        return 0;
    else if(dividend == INT_MIN && divisor == -1)  
        return INT_MAX;
    else if(dividend == INT_MIN && divisor == 1)
        return INT_MIN;
    else if(dividend == INT_MIN && divisor == INT_MIN)  
        return 1;
    else if(divisor == INT_MIN)
        return 0;

    bool negative = (dividend ^ divisor) < 0;       

    if(dividend == INT_MIN)         
    {
        dividend += abs(divisor);
        result++;
    }
    int t = abs(dividend);
    int d = abs(divisor);

    for(int i = 31; i >= 0; i--)
    {
        if((t >> i) >= d)
        {
            result += 1 << i;
            t -= d << i;
        }
    }

    return negative ? -result : result;
   
}

第30题：串联所有单词的子串
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words

思路
1.当字符串s的长度l1小于字符串words的长度总和l2，直接返回NULL；
2.字符串s每个字符开始的长度为l2的子串，与字符串words进行匹配，若可以匹配returnSize加1，否则进行下一个字符开始的子串的匹配。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int  match(char *s, char **words, int wordsSize, int l2)
 {
    int flag[wordsSize];
    memset(flag, 0, sizeof(flag));
   
    int i, j, k;
    for(i = 0; i < wordsSize; i++)
    {
    
            for(j = 0; j < wordsSize; j++)
            {
                if(flag[j] == 0)
                {
                    for(k = 0; k < l2; k++)
                    {
                        if(*(s+i*l2+k) != words[j][k]) break;
                    }
                    if(k == l2)  
                    {
                        flag[j] = 1;
                        break;
                    }
                    
                }
            }
        
    }
    for(i = 0; i < wordsSize; i++)
    {
        if(flag[i] == 0) return 0;

    }
    return 1;
 }
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
    int l1 = strlen(s);     //the length of s;
    int l2 = strlen(words[0]);   //the length of words;
    *returnSize = 0;
    
    if(l1 < l2 * wordsSize)  return NULL;     //the length of string s is shorter than the sum of the length of string words
    int i = 0;
    int *dos = (int *)malloc(sizeof(int) * l1);
    char tmp[l2 + 1];
    int flag;
    while(i <= l1-l2*wordsSize)
    {
        flag = match(s, words, wordsSize, l2);
        
        if(flag == 1) 
        {
            
            dos[*returnSize] = i;
            *returnSize += 1;
        }
        s++;
        i++;
    }
    return dos;
}