Leetcode常見鏈表問題及代碼示例
更新時間：2020年11月30日 10:40:30 作者：codeg
這篇文章主要介紹了Leetcode常見鏈表問題及代碼示例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
按規(guī)定區(qū)間反轉鏈表
思路：可以考慮成一種把前后數(shù)字的結點斷開重新組合的問題
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode *dummy = new ListNode(-1), *pre = dummy;
dummy->next = head;
for (int i = 0; i < m - 1; ++i)
pre = pre->next;
ListNode *cur = pre->next;
for (int i = m; i < n; ++i) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = pre->next;
pre->next = t;
}
return dummy->next;
}
};
分割鏈表
思路：先找到一個大于或者等于給定值的節(jié)點，然后再逐個把小于他們的值放在前面。例如本例先找到4，然后再找到3，然后把小于3的值都放在其前面
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *p=new ListNode(-1);
p->next=head;
ListNode *pre=p,*cur=head;
while(pre->next&&pre->next->val<x)
pre=pre->next;
cur=pre;
while(cur->next){
if(cur->next->val<x){
ListNode *tmp=cur->next;
cur->next=tmp->next;
tmp->next=pre->next;
pre->next=tmp;
pre=pre->next;
}else{
cur=cur->next;
}
}
return p->next;
}
};
逆序鏈表存儲數(shù)相加
思路：先建立一個p結點，然后將相加生成的新結點按順序放到p結點之后，然后再用一個新指針cur指向新鏈表的最后一位。設置一個進位計數(shù)res，當兩個結點值相加之后，可以用sum/10來表示進位，然后以sum%10來建立新的結點。最后需要注意的是最高位的進位問題，所以while結束后要，如果res為1，則再建一個值為1的結點。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *p=new ListNode(-1),*cur=p;
int res=0;
while(l1||l2){
int val1=l1?l1->val:0;
int val2=l2?l2->val:0;
int sum=val1+val2+res;
res=sum/10;
cur->next=new ListNode(sum%10);
cur=cur->next;
if(l1)
l1=l1->next;
if(l2)
l2=l2->next;
}
if(res)
cur->next=new ListNode(1);
return p->next;
}
};
順序鏈表存儲相加
思路：這道題和第2題類似，但是鏈表是從前往后遍歷，加法卻要從最低位相加，所以可以考慮改用棧來存儲放進來的數(shù)據(jù)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int sum = 0;
ListNode *res = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) {
sum += s1.top();
s1.pop();
}
if (!s2.empty()) {
sum += s2.top();
s2.pop();
}
res->val = sum % 10;
ListNode *cur = new ListNode(sum / 10);
cur->next = res;
res = cur;
sum /= 10;
}
return res->val == 0 ? res->next : res;
}
};
移除鏈表元素
思路：直接遞歸調用到鏈表末尾，然后回來，需要刪除的元素將鏈表next指針指向下一個元素即好。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(!head) return NULL;
head->next=removeElements(head->next,val);
return head->val==val?head->next:head;
}
};
刪除排序鏈表中的重復元素
思路：遞歸查找，如果head的值存在且相等，那么while循環(huán)跳過后面所有值相等的結點，如果后面if還有值相等則繼續(xù)進行遞歸。如果最后到head的值不同后，返回到head即可。<這種方式比新建鏈表存儲時間負責度高很多>
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
if (head->next && head->val == head->next->val) {
while (head->next && head->val == head->next->val) {
head = head->next;
}
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
};
刪除順序鏈表中的重復元素
思路：head結點的值和身后結點的值進行比較，如果值相同，則返回后面一個結點。最后回溯遞歸調用刪除重復結點。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head||!head->next) return head;
head->next=deleteDuplicates(head->next);
return (head->val==head->next->val)?head->next:head;
}
};
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了springboot啟動時候報錯mongodb問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
Maven發(fā)布封裝到中央倉庫時候報錯:no default secret key
這篇文章主要介紹了Maven發(fā)布封裝到中央倉庫時候報錯:no default secret key，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-12-12
這篇文章主要介紹了java使用swt顯示圖片示例，修改后就可變?yōu)閳D片瀏覽器,需要的朋友可以參考下2014-02-02
二級緩存是Mapper級別的緩存，多個SqlSession去操作同一個Mapper中的SQL語句，則這些SqlSession可以共享二級緩存，即二級緩存是跨SqlSession的，這篇文章主要介紹了Mybatis 動態(tài)sql的編寫|開啟二級緩存,需要的朋友可以參考下2023-02-02
SpringBoot中的@Conditional?注解的使用
@Conditional是Spring4新提供的注解，它的作用是按照一定的條件進行判斷，滿足條件的才給容器注冊Bean，本文主要介紹了SpringBoot中的@Conditional?注解的使用2024-01-01
這篇文章主要為大家詳細介紹了java模擬實現(xiàn)斗地主發(fā)牌小程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要給大家介紹了關于java新人基礎入門之遞歸調用的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要介紹了Java算法之堆排序代碼示例，具有一定參考價值，需要的朋友可以了解下。2017-11-11
這篇文章主要介紹了Java8 接口默認方法和靜態(tài)方法，在默認接口中使用關鍵字default聲明并提供具體實現(xiàn)，而且該方法不需要添加public關鍵字就可以公開調用，甚至你可以在其實現(xiàn)類中覆寫，帶著對默認接口的方法和小編一起探索下面文章內容的靜態(tài)方法吧2021-10-10
這篇文章主要介紹了JPA實現(xiàn)多條件分頁查詢方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07