?💕人生不滿百，常懷千歲憂💕
作者：Mylvzi?
?
文章主要內容：鏈表oj詳解?
題目一：移除元素
題目要求：
畫圖分析：?
?
代碼實現：?
struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*prev = NULL,*cur = head;//遍歷while(cur){if(cur->val == val)//相等{if(cur == head)//頭刪{head = cur->next;free(cur);cur = head;}else//中間情況{prev->next = cur->next;free(cur);cur = prev->next;}}else//不等{prev = cur;cur = cur->next;}}return head;
}題目二：（快慢指針應用）
題目要求 :?
畫圖分析：
代碼實現：
struct ListNode* middleNode(struct ListNode* head){struct ListNode*slow = head,*fast = head;//開始移動while(fast && fast->next)//循環條件{fast = fast->next->next;//一次移動兩步slow = slow->next;}return slow;
}?題目三：求倒數第K個結點
題目要求：
畫圖分析：
?代碼實現：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode*slow = pListHead,*fast = pListHead;//先讓fast走k步，使相對距離為Kwhile(k--){//如果fast是NULL,不存在fast->next，所以要單獨討論if(fast == NULL)return NULL;fast = fast->next;}//一起前進，直到fast是尾結點while(fast){fast = fast->next;slow = slow->next;}return slow;
}?總結：
快慢指針:
1.相對速度，fast一次走兩步，slow一次走一步，fast到終點，slow剛好到中間位置（fast的位置要分奇偶，奇數fast走到韋結點即可，偶數fast走到Null）
2.相對路程，求倒數第k個，先讓fast走k步，則fast和slow的相對距離一直是k，fast走到null，slow剛好走到倒數第k個
注意循環條件
題目四：合并兩個有序鏈表
題目要求：
畫圖分析：
代碼實現：?
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){//如果有一個鏈表為空，直接返回另一個鏈表即可if(list1 == NULL)return list2;if(list2 == NULL)return list1;//創建head和tail，便于進行尾插struct ListNode* head = NULL,*tail = NULL;//思路：取小的尾插while(list1 && list2)//有一個為空就推出{if(list1->val < list2->val){if(tail == NULL)//鏈表為空，直接復制{head = tail = list1;}else//不為空，進行尾插{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{if(tail == NULL)//鏈表為空，直接復制{head = tail = list2;}else//不為空，進行尾插{tail->next = list2;tail = tail->next;}list2 = list2->next;}}//出循環，證明有一個已經遍歷完if(list1)//list1未遍歷完tail->next = list1;if(list2)//list1未遍歷完tail->next = list2;return head;
}
)
)
