題目描述
給定單向鏈表的頭指針和一個(gè)要?jiǎng)h除的節(jié)點(diǎn)的值淘这，定義一個(gè)函數(shù)刪除該節(jié)點(diǎn)。
返回刪除后的鏈表的頭節(jié)點(diǎn)。
注意：此題對(duì)比原題有改動(dòng)
示例 1:
輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)坎怪，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.
示例 2:
輸入: head = [4,5,1,9], val = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個(gè)節(jié)點(diǎn)廓握，那么在調(diào)用了你的函數(shù)之后芋忿，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.
說明：
題目保證鏈表中節(jié)點(diǎn)的值互不相同
若使用 C 或 C++ 語言，你不需要 free 或 delete 被刪除的節(jié)點(diǎn)
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
解題思路
依次遍歷鏈表的每一個(gè)節(jié)點(diǎn)疾棵，直到找到值為val的節(jié)點(diǎn)，讓刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)痹仙，則可以從鏈表中刪除此節(jié)點(diǎn)是尔，不過需要注意邊界及特殊條件，即要?jiǎng)h除的是頭節(jié)點(diǎn)开仰，鏈表只有一個(gè)節(jié)點(diǎn)拟枚，指向鏈表的指針為空等情況。
代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode *pre = head;
if(head == NULL)
return NULL;
if(head->val == val)
return head->next;
while((pre->next != NULL) && (pre->next->val != val))
{
pre = pre->next;
}
if(pre->next != NULL)
{
pre->next = pre->next->next;
}
return head;
}
執(zhí)行結(jié)果
時(shí)間復(fù)雜度：O(n)众弓，空間復(fù)雜度：O(1)恩溅。
