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

符号 阅读:650 2022-03-12 16:25:28 评论:0
本文章主要介绍了【面试题】单链表逆转、字符串按单词逆转,具有不错的的参考价值,希望对您有所帮助,如解说有误或未考虑完全的地方,请您留言指出,谢谢!

问题一:单链表反转,提供空间复杂度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<<"\t"<<begin<<endl; 
        } 
        i++; 
    } 
    reverseString(s, begin, s.size()); 
}

标签:C++
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
排行榜
关注我们