單鏈表翻轉？
這是LeetCode上的題目，最後 Accepted， 但時間 8ms,如何改變演算法或者優化使其達到0ms？
ListNode* reverseList(ListNode* head)
{
ListNode* pLeft = head;
ListNode* pRight = 0;
while (pLeft)
{
pRight = head-&>next;
if (pRight)
{
head-&>next = pRight-&>next;
pRight-&>next = pLeft;
pLeft= pRight;
}
else
{
return pTemp;
}
}
return pTemp;
}
用C就 0ms，用C++就 12ms
然而真的沒有什麼卵用，最重要的就是能證明time complexity是O(N)，space complexity是O(1)，而且只需要one-pass/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* pLeft = NULL;
struct ListNode* pRight = head;
while (pRight) {
head = pRight-&>next;
pRight-&>next = pLeft;
pLeft = pRight;
pRight = head;
}
return pLeft;
}
真的沒有什麼用。。。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL) {
return NULL;
}
struct ListNode* new_list = NULL;
while (head != NULL) {
struct ListNode* elem = head;
head = head-&>next;
elem-&>next = new_list;
new_list = elem;
}
return new_list;
}
演算法複雜度的分析不是具體的時間，而是在特定的輸入規模下你的循環迭代次數，會去掉低次項和最高次數的係數項。比如這裡的反轉鏈表只要是O(n)的複雜度就好。相同表達式在不同時間可能運行的具體時間也不一樣，所以你貼的代碼是頭插法，學習的目的可以看看遞歸或者另外的非遞歸方法。
改成C再試試。
優化到0ms,然而這並沒有什麼卵用。～_～
推薦閱讀：
TAG:LeetCode |