1.1 移除鏈表元素

題目要求：給你一個鏈表的頭節點head 和一個整數val,請你刪除鏈表中所有滿足Node.val == val 的節點，并返回新的頭節點。

思路一：遍歷鏈表，遇到val就刪除，pcur指向val的下一個節點，最后只剩下沒有val的鏈表。

思路二：創建新的鏈表，頭節點用newHead，尾插newTail,pcur來遍歷原鏈表，當pcur!=val,就把數值拿下來，尾插到newTail中，最后新的鏈表中沒有val。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)//指向頭節點的指針，要刪除的數值
{//創建一個新鏈表ListNode* newHead, *newTail;newHead = newTail = NULL;//遍歷原鏈表ListNode* pcur = head;while (pcur)//pcur!=NULL{//找值不為val的節點，尾插到新鏈表中if (pcur->val != val){//當鏈表為空時if (newHead == NULL){newHead = newTail = pcur;}else//鏈表不為空{newTail->next = pcur;//將pcur的值插入newTail的下一個節點newTail = newTail->next;//最后讓newTail走向下一個節點}pcur = pcur->next;}}if (newTail)//newTail!=NULLnewTail->next = NULL;return newHead;
}

1.2 反轉鏈表

思路一：創建新的鏈表，將原鏈表中的節點拿過來頭插。

思路二：創建三個指針，完成鏈表的翻轉。

//反轉鏈表
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//判斷鏈表是否為空if(head==NULL)return head;ListNode* n1,*n2,*n3;//創建三個指針實現反轉//介紹三個指針分別在什么地方n1 = NULL, n2 = head, n3 = n2->next;while(n2)//判斷結束節點，n2!=NULL{n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;//n1是鏈表新的頭節點
}

1.3 鏈表的中間節點

思路一：遍歷原鏈表，count計節點數，直接返回（count / 2)節點的next節點

思路二：快慢指針

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//創建兩個指針ListNode* fast,* slow;fast=head;slow=head;//兩個創建的指針都指向head頭節點while(fast && fast->next)//偶數鏈表遍歷結束條件fast=NULL,奇數鏈表遍歷結束條件fast->next=NULL{slow=slow->next;fast=fast->next->next;}return slow;
}

問題：while(fast->next && fast)可以交換位置嗎？

不可以！若鏈表有偶數個節點的情況下，fast最后一次會直接走到空，fast->next會執行報錯！

1.3.1拓展提升：刪除鏈表的中間節點

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* deleteMiddle(struct ListNode* head) {struct ListNode* slow, *fast, *dummy, *tmp;dummy=(struct ListNode*)malloc(sizeof( ListNode));dummy->next=head;slow = fast = dummy;while(fast->next != NULL && fast->next->next != NULL) {slow = slow->next;fast = fast->next->next;}tmp = slow->next;slow->next = tmp->next;free(tmp);return dummy->next;
}

問題：為什么要額外申請一個空間放置dummy,dummy->next=head,頭節點head本身就是存在的，為什么要有一個dummy來指向head?

答： dummy(虛擬頭節點）使用來簡化邊界情況處理的“工具人”。如果鏈表只有一個節點，這個唯一節點就是“中間節點”，需要被刪除，如果沒有dummy,直接刪除head,結果會返回NULL,而dummy->next永遠指向實際鏈表的頭節點，不管頭節點有沒有被刪除，最后返回的都是dummy->next,不用單獨處理頭節點被刪除導致head無效的情況。

博主的下一篇博客：單鏈表專題---暴力算法美學(2)(有視頻演示）-CSDN博客