【面试题】单链表逆转、字符串按单词逆转

问题一：单链表反转，提供空间复杂度O(1)，时间复杂度O(n)，

解法：利用三个指针遍历一遍，下面用图来阐释。

图1，初始情况，给定head指针，链表末尾指向NULL。

图2，创建三个节点指针，分别为p指向head，q指向p->next，r指向q->next。并且将p指向NULL，因为逆转链表之后，最开始的头结点将变成尾节点，head->next = NULL

图3，将q的next节点指向p，即q->next = p.

图4，三个指针分别向后移动一位，p = q， q = r， r = r->next。

循环终止的条件是r == NULL，这时还需要将最后一个节点指向前一个节点，即q->next = p, 并且把q赋给head，完成逆转。

代码：

 1 LinkedList* reverse(LinkedList* head)
 2 {
 3     if(head == NULL) return head;
 4     LinkedList *p, *q, *r;
 5     p = head;
 6     q = p->next;
 7     r = q->next;
 8     head->next = NULL;
 9     while(r)
10     {
11         q->next = p;
12         p = q;
13         q = r;
14         r = r->next;
15     }
16     q->next = p;
17     head = q;
18     return head;
19 }

问题二：O（1）空间复杂度、O（n）时间复杂度，要求将一个字符串按单词逆转，比如 This is a sentence，变成sentence a is This

代码：

//设计算法实现字符串逆序存储，要求不另设串存储空间
void swap(string & s, int i, int j)
{
    char tmp = s[i];
    s[i] = s[j];
    s[j] = tmp;
}

void reverseString(string &s, int begin, int end)
{
    for(int i=begin; i<(end + begin)/2; ++i)
        swap(s, i, end-1-i+begin);
}

//先整体逆序，再按单词逆序
void reverseWord(string &s)
{
    reverseString(s, 0, s.size());
    //cout<<s<<endl;
    int begin = 0, i = 0;
    while(i<s.size())
    {
        if(s[i] == ' ')
        {
            reverseString(s, begin, i);
            begin = i + 1;
            //cout<<i<<"	"<<begin<<endl;
        }
        i++;
    }
    reverseString(s, begin, s.size());
}