leetcode (27)移除元素
- 基于順序表
🙉：題目
給你一個陣列 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并回傳移除后陣列的新長度，
不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并 原地修改輸入陣列，元素的順序可以改變，你不需要考慮陣列中超出新長度后面的元素，
🙊:案例
🐒：思路
快慢針：
- 創建dest和sur指標
- sur去找val值如果不是就吧sur賦值給dest
- sur等于val則一直迭代
圖解：
🐵：代碼
int removeElement(int* nums, int numsSize, int val)
{
int strc =0;
int dest=0;
while(strc<numsSize)
{
if(nums[strc]==val)
{
strc++;
}
else
{
nums[dest]=nums[strc];
dest++;
strc++;
}
}
return dest;
}
leetcode (26) 洗掉陣列重復項
🙉：題目
給你一個有序陣列 nums ，請你 原地
洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，
不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成
🙊:案例
🐒：思路
快慢指標
- 創建dest和sur指標
- 不同sur與dest是否相同，不同賦值dest+1(不是dest+1那么
頭元素就被覆寫了) - 相同sur迭代
圖解
🐵：代碼
int removeDuplicates(int* nums, int numsSize)
{
int strc =0;
int dest=0;
while(strc<numsSize)
{
if(nums[strc]==nums[dest])
{
strc++;
}
else
{
dest++;
nums[dest]=nums[strc];
strc++;
}
}
if(numsSize!=0)
{
return dest+1;
}
return 0;
}
注意他可能傳的是空陣列，如果為空那么回傳dest+1列印就越界了
leetcode (88) 合并倆個有序陣列
🙉：題目
給你
兩個有序整數陣列nums1 和 nums2，請你將 nums2合并到 nums1中，使 nums1 成為一個有序陣列，
初始化 nums1 和 nums2 的元素數量分別為 m 和 n ，你可以假設 nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來自 nums2 的元素，
🙊:案例
🐒：思路
思路一（暴力解法）：
- 直接把陣列二插入陣列一后面
- qsort排序
圖解
🐵：代碼
int compar(const void *p1,const void*p2)
{
return (*(int*)p1)-(*(int*)p2);
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int a=m;
for(int i =0;i<n;i++)
{
nums1[a]=nums2[i];
a++;
}
qsort(nums1,n+m,sizeof(int),compar);
}
思路二
- 都指向需要比最后的元素
- 比較倆陣列大小，大的放到一陣列最后一個位置
- 依次迭代迭代
圖解
🐵：代碼
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int i1=m-1,i2=n-1;
int tail=m+n-1;
while(i1>=0&&i2>=0)
{
if(nums1[i1]>nums2[i2])
nums1[tail--]=nums1[i1--];
else
nums1[tail--]=nums2[i2--];
}
while(i2>=0)
{
nums1[tail--]=nums2[i2--];
}
}
leetcode (203) 移除鏈表元素
🙉：題目
給你一個鏈表的頭節點 head 和一個整數 val ，請你
洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，
🙊:案例
🐒：思路
思路一
- 把指標給cur
- cur找cur下一個節點的值是否和val一樣
- 一樣釋放，不一樣迭代
- 注意（頭的值也可能等于val），（且可能是空鏈表）
圖解
🐵：代碼
struct ListNode* removeElements(struct ListNode* head, int val)//回傳指標介面
{
if(head==NULL)
{
return NULL;
}
struct ListNode* cur=head;
struct ListNode* hind=head;
while(cur->next)
{
if(cur->next->val==val)
{
struct ListNode*next=cur->next->next;
free(cur->next);
cur->next=next;
}
else
{
cur=cur->next;
}
}
if(head->val==val)
{
struct ListNode*next=head->next;
free(head);
head=next;
}
return head;
}
思路二
- 三個指標，cur，list，tail
- cur找相等val的值
- list為這個新鏈表的頭
- tail為cur的上一個節點
- 找到free，迭代
- 沒找到吧cur給tail，迭代
如圖所示
🐵：代碼
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode*cur=head;
struct ListNode*list=NULL; struct ListNode*tail=NULL;
while(cur)
{
struct ListNode*next=cur->next;
if(cur->val==val)
{
free(cur);
}
else
{
if(list==NULL)
{
list=cur;
tail=list;
}
else
{
tail->next=cur;
}
}
cur=next;
}
return list;
}
leetcode (206) 反轉鏈表
🙉：題目
給你單鏈表的頭節點 head ，請你
反轉鏈表，并回傳反轉后的鏈表
🙊:案例
🐒：思路
思路一
創建節點法：
- 在老節點后面創建新節點（應為頭插會
改變原來鏈表的順序死回圈） - 剝離開辟的節點插入新鏈表
- 鏈接老鏈表與節點
- 迭代（這種方法不太推薦容易搞混且效率不是很高)
🐵：代碼
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newlist=NULL;
struct ListNode*cur=head;
while(cur)//在老節點后插入一個新節點
{
struct ListNode*next=cur->next;
struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
newnode->next=next;
newnode->val=cur->val;
cur->next=newnode;
cur=cur->next->next;
}
cur=head;
while(cur)//剝離新節點并插入到新鏈表上
{
struct ListNode* curnext=cur->next;
cur=curnext->next;
curnext->next=NULL;
if(newlist==NULL)
{
newlist=curnext;
}
else
{
struct ListNode*oldhead =newlist;
newlist=curnext;
newlist->next=oldhead;
}
}
return newlist;
}
思路二
翻轉鏈表法：
- 反轉鏈表鏈接順序
- 頭變尾，尾變頭
- 三個指標完成置換
如圖所示：
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
struct ListNode*n1=NULL;
struct ListNode*n2=head;//頭
struct ListNode*n3=head->next;//頭后面一個節點
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3!=NULL)
n3=n3->next;
}
return n1;
}
牛客 鏈表倒數第k個節點
🙉：題目
輸入一個鏈表，輸出該鏈表中倒數第k個結點，
其實就是從后往前數第k個節點
🙊:案例
🐒：思路
快慢指標
- 快指標先走k步（題比較陰間：
給你一個空鏈表） - 然后慢指標在和塊指標一起走
- 代碼很簡單，但是想法很難
- （這個方法一般人可想不到，幸好我不是一般人，我是二般人，好吧我也是一般人，大佬思路，多提一嘴，孰能生巧(
勤加練習+復盤)+多見風浪(多刷題)，以后碰到hr都不慌）
圖解：
🐵：代碼
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
ListNode* fast=pListHead;
ListNode* slow=pListHead;
while(k--)
{
if(fast==NULL)
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
leetcode (879) 鏈表的中間節點
🙉：題目
給定一個頭結點為 head 的非空單鏈表，
回傳鏈表的中間結點,如果有兩個中間結點，則回傳第二個中間結點，
🙊:案例
🐒：思路
快慢指標
- fast走倆步
- slow走一步
- 這樣就可以取到中間節點
- 注意鏈表可能會有
基數個or偶數個節點，所以要迭代的話條件要滿足
圖解：
🐵：代碼
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
leetcode (21)合并連個有序鏈表
🙉：題目
將兩個
升序鏈表合并為一個新的升序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
🙊:案例
🐒：思路
思路一：
一一對比法
- 倆鏈表從前往后一一對比
- 小的尾插到新鏈表
🐵：代碼
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1==NULL&&l2==NULL)
{
return NULL;
}
struct ListNode*newlist=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*cur=newlist;
while(l1&&l2)
{
if(l1->val<l2->val)
{
cur->next=l1;
l1=l1->next;
}
else
{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
if(l1==NULL)
cur->next=l2;
if(l2==NULL)
cur->next=l1;
struct ListNode*head=newlist->next;
free(newlist);
return head;
}
這里用到了
帶頭單鏈表，俗稱哨兵位，（其實也可以不用）
思路二：
直插法
3. 判斷倆個連表的頭節點小的付給新鏈表
4. 一一對比
5. 上面方法的另一種
🐵：代碼
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
struct ListNode*n1=l1;
struct ListNode*n2=l2;
struct ListNode*newhead=NULL;
struct ListNode*tail=NULL;
if(n1->val < n2->val)
{
newhead=tail=n1;
n1=n1->next;
}
else
{
newhead=tail=n2;
n2=n2->next;
}
while(n1&&n2)
{
if(n1->val<n2->val)
{
tail->next=n1;
tail=n1;
n1=n1->next;
}
else
{
tail->next=n2;
tail=n2;
n2=n2->next;
}
}
if(n1)
tail->next=n1;
if(n2)
tail->next=n2;
return newhead;
思路三：
直插法2
- 判斷倆個連表的頭節點小的付給新鏈表
- 一一直接插入到練表中更改他們的鏈接方式（這個就留給你去寫吧）
牛客 (綜合題) 鏈表的回文結構
🙉：題目
對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的演算法，判斷其是否為回文結構，
給定一個鏈表的頭指標A，請回傳一個bool值，代表其是否為回文結構，保證鏈表長度小于等于900，
🙊:案例
其實就是這個鏈表是不是中心對稱
🐒：思路
快慢指標，翻轉鏈表，比大小
- 找到中間值（快慢指標）
- 從中間值開始反轉成為一個新的鏈表(翻轉鏈表)
- 一一比大小
- 👆有動圖詳解
🐵：代碼
class PalindromeList {
public:
ListNode* listmiddle(ListNode* A)
{
ListNode*fast=A;
ListNode*slow=A;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
ListNode* reverse(ListNode* middle)
{
ListNode* cur=middle;
ListNode*tail=NULL;
while(cur)
{
ListNode*next=cur->next;
cur->next=tail;
tail=cur;
cur=next;
}
return middle;
}
bool chkPalindrome(ListNode* A)
{
ListNode*middle=listmiddle(A);
ListNode*B=reverse(middle);
while(A&&B)
{
if(A->val!=B->val)
{
return false;
}
A=A->next;
B=B->next;
}
return true;
}
};
leetcode (160) 相交鏈表
🙉：題目
給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并回傳兩個單鏈表
相交的起始節點，如果兩個鏈表沒有交點，回傳 null，
圖示兩個鏈表在節點 c1 開始相交：
🙊:案例
🐒：思路
快慢指標
- 先比較倆個鏈表的長度并求出差值
- 快的先走差值步
- 然后在一起走，一一比較（比較的是
地址）
圖解：
🐵：代碼
int size(struct ListNode *head)
{
int count=0;
while(head)
{
++count;
head=head->next;
}
return count;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
int countA=size(headA);
int countB=size(headB);
//你不知道那個大其實也可以比較count,這里就是少寫了一個else
struct ListNode*fast=headA;
struct ListNode*slow=headB;
if(countA<countB)
{
fast=headB;
slow=headA;
}
int foot=abs(countA-countB);
while(foot--)
{
fast=fast->next;
}
while(fast&&slow)
{
if(fast==slow)
{
return fast;
}
fast=fast->next;
slow=slow->next;
}
return NULL;
}
abs絕對值函式
leetcode (206) 反轉鏈表
🙉：題目
給定一個鏈表，判斷鏈表中是
否有環，
如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環， 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，
如果鏈表中存在環，則回傳 true ， 否則，回傳 false ，
🙊:案例
🐒：思路
快慢指標
- 快指標走倆步
- 慢指標走一步
- 然后在途中會遇到
🐵：代碼
bool hasCycle(struct ListNode *head)
{
struct ListNode *fast,*slow;
fast=slow=head;
while (fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
return true;
}
}
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294712.html
標籤：其他
上一篇：list模擬實作