leetcode刷題筆記（1）：簡單題（連結清單）C++
文章目錄
-
- leetcode刷題筆記（1）：簡單題（連結清單）C++
- 141、環形連結清單
- 160、相交連結清單
- 203、移除連結清單元素
- 206、反轉連結清單
- 225、用隊列實作棧
- 面試題10.01、合并排序的數組
- 234、回文連結清單
- 237、删除連結清單中的節點（智商題）
- 326、3的幂
- 344、反轉字元串
- 876、連結清單的中間結點
- 1290、二進制連結清單轉整數
141、環形連結清單
問題
給定一個連結清單，判斷連結清單中是否有環。
為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：連結清單中沒有環。
進階：
你能用 O(1)（即，常量）記憶體解決此問題嗎？
代碼模闆
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
}
};
題解
我的方法
周遊連結清單的同時，記錄每一個節點指針，判斷目前節點的
next
是否指向儲存的節點指針清單。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
vector<ListNode*> tmp; //用set更好！！！
ListNode* cur=head;
while(cur != NULL){
tmp.push_back(cur);
for(auto ptr : tmp){
if(cur->next==ptr)
return true;
}
cur = cur->next;
}
return false;
}
};
- 時間複雜度O(N)
- 空間複雜度O(N)
雙指針O(1)法
通過使用具有 不同速度 的快、慢兩個指針周遊連結清單，空間複雜度可以被降低至 O(1)O(1)。慢指針每次移動一步，而快指針每次移動兩步。
如果清單中不存在環，最終快指針将會最先到達尾部，此時我們可以傳回 false。
現在考慮一個環形連結清單，把慢指針和快指針想象成兩個在環形賽道上跑步的運動員（分别稱之為慢跑者與快跑者）。而快跑者最終一定會追上慢跑者。這是為什麼呢？考慮下面這種情況（記作情況 A）- 假如快跑者隻落後慢跑者一步，在下一次疊代中，它們就會分别跑了一步或兩步并相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL || head->next==NULL)
return false;
ListNode* slow=head;
ListNode* fast=head->next;
while(fast != slow){
if(fast==NULL || fast->next==NULL )
return false;
slow=slow->next;
fast = fast->next->next;
}
return true;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
160、相交連結清單
題目
編寫一個程式，找到兩個單連結清單相交的起始節點。
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節點的值為 8 （注意，如果兩個連結清單相交則不能為 0）。從各自的表頭開始算起，連結清單 A 為 [4,1,8,4,5]，連結清單 B 為 [5,0,1,8,4,5]。在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
題解
**first **
最笨的方法！！固定連結清單A，從連結清單B頭節點開始，依次判斷是否等于A中的節點。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur = headA;
while(cur != NULL){
ListNode *tmp = headB;
while(tmp != NULL){
if(tmp==cur)
return tmp;
tmp = tmp->next;
}
cur = cur->next;
}
return NULL;
}
};
- 時間複雜度O(NM)
- 空間複雜度O(1)
second
先算出兩個連結清單的長度，将長 的那個連結清單的指針ptr移動 AB長度差個機關，即使AB的目前指針對齊，目前指針的後面連結清單長度相等。再同時滑動兩個指針，直至指針相等。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int la=0,lb=0;
ListNode *ptrA = headA,*ptrB = headB;
while(ptrA!=NULL){
la++;
ptrA = ptrA->next;
}
while(ptrB != NULL){
lb++;
ptrB = ptrB->next;
}
ptrA=headA;
ptrB=headB;
if(la>lb){
for(int i=0;i<la-lb;i++)
ptrA = ptrA->next;
}
if(lb>la){
for(int i=0;i<lb-la;i++)
ptrB = ptrB->next;
}
while(ptrA != ptrB){
ptrA = ptrA->next;
ptrB = ptrB->next;
}
return ptrA;
}
};
- 時間複雜度O(N+M)
- 空間複雜度O(1)
浪漫————解法
錯的人遲早會走散，而對的人遲早會相逢！
A和B兩個連結清單長度可能不同，但是A+B和B+A的長度是相同的，是以周遊A+B和周遊B+A一定是同時結束。 如果A,B相交的話A和B有一段尾巴是相同的，是以兩個周遊的指針一定會同時到達交點 如果A,B不相交的話兩個指針就會同時到達A+B（B+A）的尾節點!
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* ptrA=headA,*ptrB = headB;
while(ptrA != ptrB){
ptrA = ptrA==NULL ? headB:ptrA->next;
ptrB = ptrB==NULL ? headA:ptrB->next;
}
return ptrA;
}
};
- 時間複雜度 : O(m+n)
- 空間複雜度 : O(1)
203、移除連結清單元素
題目
删除連結清單中等于給定值 val 的所有節點。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
題解
哨兵節點法
如果要删除的點位于連結清單頭節點時，比較難操作，是以建立一個哨兵節點。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* sentinel = new ListNode(0);
sentinel->next = head;
ListNode *prev = sentinel, *curr = head, *toDelete = nullptr;
while (curr != nullptr) {
if (curr->val == val) {
prev->next = curr->next;
toDelete = curr;
} else prev = curr;
curr = curr->next;
if (toDelete != nullptr) {
delete toDelete;
toDelete = nullptr;
}
}
ListNode *ret = sentinel->next;
delete sentinel;
return ret;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
無需哨兵法
巧妙之處在于，先不管第一個節點，先把後面的去掉，最後隻有第一個節點可能需要删除，不必考慮其他節點了；🐂🍺
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(!head)
return nullptr;
ListNode* p = head, *q;
while(p->next)
{
if(p->next->val == val)
{
q = p->next;
p->next = q->next;
delete q;
}
else
p = p->next;
}
return head->val == val ? head->next : head; //此處隻需考慮第一個節點
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
萬事皆可遞歸法
無情遞歸
class Solution
{
public ListNode removeElements(ListNode head, int val)
{
if (head == null)
return head;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
- 空間複雜度O(N)
- 時間複雜度O(N)
206、反轉連結清單
題目
反轉一個單連結清單。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:你可以疊代或遞歸地反轉連結清單。你能否用兩種方法解決這道題？
題解
-
我的方法
使用
last
next
cur
cur
cur->next
last
next
cur
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head,*last=NULL,*next;
while(cur != NULL)
{
next = cur->next;
cur->next = last;
last = cur;
cur = next;
}
return last;
}
};
- 最短時間
使用了遞歸。将傳入的連結清單分成兩部分，第一個節點和剩餘節點組成的連結清單，若要反轉連結清單，隻需反轉第一個節點和剩餘節點的反轉連結清單；剩餘節點的反轉連結清單可以遞歸使用函數求出。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head ->next)
return head;
ListNode* newHead = reverseList(head ->next);
head ->next ->next = head;
head ->next = nullptr;
return newHead;
}
};
225、用隊列實作棧
題目
使用隊列實作棧的下列操作：
push(x) – 元素 x 入棧
pop() – 移除棧頂元素
top() – 擷取棧頂元素
empty() – 傳回棧是否為空
注意:
你隻能使用隊列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
你所使用的語言也許不支援隊列。 你可以使用 list 或者 deque（雙端隊列）來模拟一個隊列 , 隻要是标準的隊列操作即可。
你可以假設所有操作都是有效的（例如, 對一個空的棧不會調用 pop 或者 top 操作）。
題解
題意應該是讓用單向隊列來解決的，有些題解直接用的雙向隊列，鄙視！！
單向隊列也很簡單，唯一需要注意的是
push
操作，棧需要在棧頂
push
，而隊列隻能一頭
pop
，一頭
push
，我用的是隊首當棧頂，是以隊列
push
的時候，需要依次把隊首的元素插到隊尾，進而使新
push
的元素處于隊首，也就是棧頂。
class MyStack {
private:
queue<int> q;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
q.push(x);
for(int i=0;i<q.size()-1;i++){
q.push(q.front());
q.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int x=q.front();
q.pop();
return x;
}
/** Get the top element. */
int top() {
return q.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
面試題10.01、合并排序的數組
題目
給定兩個排序後的數組 A 和 B，其中 A 的末端有足夠的緩沖空間容納 B。 編寫一個方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素數量分别為 m 和 n。
示例:
輸入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]
說明:
A.length == n + m
題解
投機取巧（鄙視我自己解法）：用C++自帶的
sort
算法求解。（
insert
是插入，會造成A的空間變大，A中的0并不會消失，是以使用
resize
重新配置設定A的空間）
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
A.insert(A.begin()+m,B.begin(),B.end());
A.resize(m+n);
sort(A.begin(),A.end());
}
};
-
時間複雜度：O((m+n)\log(m+n))
排序序列長度為 m+n，套用快速排序的時間複雜度即可，平均情況為 O((m+n)\log(m+n))
-
空間複雜度：O(\log(m+n))
排序序列長度為 m+n，套用快速排序的空間複雜度即可，平均情況為 O(\log(m+n))
解法二：
反向排序，先排最大的；是以A後面又足夠的位置，以至于A不會被覆寫元素
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int pa = m - 1, pb = n - 1;
int tail = m + n - 1;
int cur;
while (pa >= 0 || pb >= 0) {
if (pa == -1)
cur = B[pb--];
else if (pb == -1)
cur = A[pa--];
else if (A[pa] > B[pb])
cur = A[pa--];
else
cur = B[pb--];
A[tail--] = cur;
}
}
};
-
時間複雜度：O(m+n)
指針移動單調遞減，最多移動 m+nm+n 次，是以時間複雜度為 O(m+n)
-
空間複雜度：O(1)
直接對數組 A 原地修改，不需要額外空間
234、回文連結清單
問題
請判斷一個連結清單是否為回文連結清單。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進階：
你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？
題解
笨方法
修改連結清單結構，使前一半反向，再周遊兩個半連結清單！修改了連結清單一般不可取！！！
是以修改了輸入的連結清單一般使用完，要恢複的原來的結構。（我懶的改回去了）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL || head->next == NULL)
return true;
int l=0;
ListNode* ptr = head;
while(ptr != NULL){
l++;
ptr = ptr->next;
}
ptr = head;
ListNode *tmp=NULL,*tmp1 = head;
for(int i=0;i<l/2;i++){
ptr = tmp1;
tmp1 = ptr->next;
ptr->next = tmp;
tmp = ptr;
}
tmp1 = l%2==0?tmp1:tmp1->next;
while(ptr != NULL ){
if(ptr->val != tmp1->val)
return false;
ptr = ptr->next;
tmp1 = tmp1->next;
}
return true;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
黃金更新版
應用了快慢指針法，再周遊的同時，使連結清單的前一半逆向。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head||!head->next) return true;
auto fast=head,slow=head;
ListNode* p,*pre=NULL;
while(fast&&fast->next){
p=slow;
slow=slow->next;
fast=fast->next->next;
p->next=pre;
pre=p;
}
if(fast) slow=slow->next;
while(p){
if(p->val!=slow->val) return false;
p=p->next;
slow=slow->next;
}
return true;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
237、删除連結清單中的節點（智商題）
問題
請編寫一個函數，使其可以删除某個連結清單中給定的（非末尾）節點，你将隻被給定要求被删除的節點。
- 示例 1:
輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你連結清單中值為 5 的第二個節點，那麼在調用了你的函數之後，該連結清單應變為 4 -> 1 -> 9.
- 示例 2:
輸入: head = [4,5,1,9], node = 1
輸出: [4,5,9]
解釋: 給定你連結清單中值為 1 的第三個節點，那麼在調用了你的函數之後，該連結清單應變為 4 -> 5 -> 9.
代碼模闆
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
}
};
提示
引用一個評論：
這道題細思極恐：如何讓自己在世界上消失，但又不死？ —— 将自己完全變成另一個人，再殺了那個人就行了。
題解
無語題，這題出的，不就是數組删除節點的做法嗎？（隻給了
ListNode* node
要删除的節點，其他一律沒有！！）
my way
我是把之後的節點依次複制到前一節點，最後删除最後一個節點。
然而我這做法也笨了，思路窄了窄了！！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
while(node->next->next != NULL){
node->val = node->next->val;
node = node->next;
}
ListNode* tmp = node->next;;
node->val = node->next->val;
node->next = NULL;
delete tmp;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
好一點的方法
比我的好多了！！
隻将下一節點複制到要删除的節點，然後目前節點跳到下下節點，删除下一節點。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
ListNode *tmp = node->next;
node->next = tmp->next;
delete tmp;
}
};
- 時間複雜度O(1)
- 空間複雜度O(1)
326、3的幂
問題
給定一個整數，寫一個函數來判斷它是否是 3 的幂次方。
示例 1:
輸入: 27
輸出: true
示例 2:
輸入: 0
輸出: false
示例 3:
輸入: 9
輸出: true
題解
我的辣子雞方法
class Solution {
public:
bool isPowerOfThree(int n) {
for(int i=0;i<n;i++){
if(pow(3,i) == n)
return true;
if(pow(3,i)> n)
return false;
}
return false;
}
};
- 時間複雜度O(N) :将pow複雜度視為O(1)，可能不太對
- 空間複雜度O(1)
無情遞歸
不會做就遞歸系列
class Solution {
public:
bool isPowerOfThree(int n) {
if (n==1)
return true;
else if (n>0 && n%3==0)
return isPowerOfThree(n/3);
else
return false;
}
};
- 時間複雜度O(N)
- 空間複雜度O(N)
循環疊代法
class Solution {
public:
bool isPowerOfThree(int n) {
if (n < 1) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}
-
時間複雜度：O(log_b(n))。除數是用對數表示的。
空間複雜度：O(1)，沒有使用額外的空間。
整數限制
無法言語
可以看出 n 的類型是 int。在 Java 中說明了該變量是四個位元組，他的最大值為 2147483647。有三種方法可以計算出該最大值。
System.out.println(Integer.MAX_VALUE);
MaxInt = 2^{32} /2-1,因為我們使用 32 位來表示數字，是以範圍的一半用于負數，0 是正數的一部分。
知道了 n 的限制，我們現在可以推斷出 n 的最大值，也就是 3 的幂，是 1162261467。
class Solution {
public：
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
- 時間複雜度O(1)
- 空間複雜度 O(1)
344、反轉字元串
題目
編寫一個函數，其作用是将輸入的字元串反轉過來。輸入字元串以字元數組 char[] 的形式給出。
不要給另外的數組配置設定額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
你可以假設數組中的所有字元都是 ASCII 碼表中的可列印字元。
示例 1：
輸入：["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
示例 2：
輸入：["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
題解
my way
很簡單，用一個
char
的額外空間即可。兩頭互相交換，直到相遇。
class Solution {
public:
void reverseString(vector<char>& s) {
char tmp;
for(int i=0;i<s.size()/2;i++){
tmp=s[i];
s[i]=s[s.size()-i-1];
s[s.size()-1-i]=tmp;
}
}
};
- 空間複雜度 O(1) 隻是用了一個額外空間
- 時間複雜度O(n) 一次循環交換2個值，是以最多有n/2次交換，是以為O(n)
最簡潔方法
使用自帶算法（耍賴），
class Solution {
public:
void reverseString(vector<char>& s) {
reverse(s.begin(),s.end());
}
};
- 空間複雜度 ？？
- 時間複雜度 ？？
遞歸
遞歸需要堆棧空間
class Solution {
public:
void reverseString(vector<char>& s) {
helper(s, 0, s.size());
}
void helper(vector<char>& s, int pos, int s_len){
if ( pos >= s_len / 2) return;
char tmp = s[pos];
s[pos] = s[s_len - 1 - pos];
s[s_len - 1 - pos ] = tmp;
helper(s, pos+1, s_len);
}
};
- 空間複雜度O(N) 執行了N/2次交換
- 時間複雜度O(N).遞歸過程中使用了堆棧空間
876、連結清單的中間結點
題目
給定一個帶有頭結點 head 的非空單連結清單，傳回連結清單的中間結點。
如果有兩個中間結點，則傳回第二個中間結點。
示例 1：
輸入：[1,2,3,4,5]
輸出：此清單中的結點 3 (序列化形式：[3,4,5])
傳回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。
注意，我們傳回了一個 ListNode 類型的對象 ans，這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
輸入：[1,2,3,4,5,6]
輸出：此清單中的結點 4 (序列化形式：[4,5,6])
由于該清單有兩個中間結點，值分别為 3 和 4，我們傳回第二個結點。
題解
快慢指針法
根據141題的快慢指針法來的靈感
好吧，其實一模一樣的解法，不過更簡單點
兩個指針，一個一次走一步，另一個一次走兩步，當塊的那個走到結尾的時候，慢的指針正好走到一半
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(true){
if(fast==NULL || fast->next==NULL)
return slow;
slow = slow->next;
fast = fast->next->next;
}
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
單指針法
先周遊一次，求得連結清單長度，在周遊一半即可
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int n = 0;
ListNode* cur = head;
while (cur != nullptr) {
++n;
cur = cur->next;
}
int k = 0;
cur = head;
while (k < n / 2) {
++k;
cur = cur->next;
}
return cur;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
1290、二進制連結清單轉整數
題目
給你一個單連結清單的引用結點 head。連結清單中每個結點的值不是 0 就是 1。已知此連結清單是一個整數數字的二進制表示形式。
請你傳回該連結清單所表示數字的 十進制值 。
示例 1：
輸入：head = [1,0,1]
輸出：5
解釋：二進制數 (101) 轉化為十進制數 (5)
示例 2：
輸入：head = [0]
輸出：0
示例 3：
輸入：head = [1]
輸出：1
示例 4：
輸入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
輸出：18880
示例 5：
輸入：head = [0,0]
輸出：0
提示：
連結清單不為空。
連結清單的結點總數不超過 30。
每個結點的值不是 0 就是 1。
題解
簡單的不能再簡單的移位操作
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int getDecimalValue(ListNode* head) {
int d=0;
ListNode* ptr = head;
while(ptr != NULL){
d = d*2+ptr->val;
ptr = ptr->next;
}
return d;
}
};
- 時間複雜度O(N)
- 空間複雜度O(1)
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)