1.咕

203. 移除鏈表元素 - 力扣（LeetCode）

給你一個鏈表的頭節點?head?和一個整數?val?，請你刪除鏈表中所有滿足?Node.val == val?的節點，并返回?新的頭節點?

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newnode=NULL;struct ListNode* newhead=NULL;while(head){if(head->val!=val)//進行一個尾插就行了{if(newnode==NULL){newnode=head;newhead=head;}else{newnode->next=head;newnode=newnode->next;}}head=head->next;}if(newnode)newnode->next=NULL;return newhead;
}

2.咕咕

206. 反轉鏈表 - 力扣（LeetCode）

給你單鏈表的頭節點?head?，請你反轉鏈表，并返回反轉后的鏈表。

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* l1=NULL;struct ListNode* l2=head;while(l2!=NULL){struct ListNode* l3=l2->next;l2->next=l1;l1=l2;l2=l3;}return l1;
}
//定義3個指針NULL   1  ->  2  ->  3  ->  NULLl1<-   l2<-   l3l1<-   l2 <-  l3

3.咕咕咕

876. 鏈表的中間結點 - 力扣（LeetCode）

給你單鏈表的頭結點?head?，請你找出并返回鏈表的中間結點。

如果有兩個中間結點，則返回第二個中間結點。

struct ListNode* middleNode(struct ListNode* head) {if(head==NULL) return NULL;struct ListNode* l1=head;struct ListNode* l2=head;while(l2&&l2->next){l1=l1->next;l2=l2->next->next;}return l1;
}
//快慢指針，找鏈表中點

4.咕咕咕咕

21. 合并兩個有序鏈表 - 力扣（LeetCode）

將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL) return list2;if(list2==NULL) return list1;struct ListNode* l1=list1;struct ListNode* l2=list2;
//申請一個“哨兵位”，放在最前面，可以簡化一會尾插的代碼，不用考慮尾插時鏈表為空的情況struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* pcur=newhead;while(l1&&l2){if(l1->val>l2->val){pcur->next=l2;l2=l2->next;}else{pcur->next=l1;l1=l1->next;}pcur=pcur->next;}if(l1) pcur->next=l1;if(l2) pcur->next=l2;newhead=newhead->next;return newhead;
}

5.咕咕咕咕咕

鏈表的回文結構_牛客題霸_牛客網

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。

給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

class PalindromeList {
public:bool chkPalindrome(ListNode* head) {if(head == nullptr || head->next == nullptr) return true;
//先快慢指針找中點ListNode* slow = head;ListNode* fast = head;while(fast && fast->next) {slow = slow->next;fast = fast->next->next;}
//中點之后的鏈表反轉ListNode* reversed = nullptr;ListNode* current = slow;while(current) {ListNode* nextNode = current->next;current->next = reversed;reversed = current;current = nextNode;}
//進行比對ListNode* p1 = head;ListNode* p2 = reversed;bool isPalindrome = true;while(p1 && p2) {if(p1->val != p2->val) {isPalindrome = false;break;}p1 = p1->next;p2 = p2->next;}return isPalindrome;}
};

6.咕咕咕咕咕咕

鏈表分割_牛客題霸_牛客網

現有一鏈表的頭指針 ListNode*?pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。

ListNode* partition(ListNode* pHead, int x) {if(pHead == nullptr || pHead->next == nullptr) return pHead;ListNode* smallDummy = new ListNode(0); // 小值鏈表的虛擬頭節點ListNode* bigDummy = new ListNode(0);   // 大值鏈表的虛擬頭節點ListNode* small = smallDummy;ListNode* big = bigDummy;ListNode* pcur = pHead;while(pcur != nullptr) {if(pcur->val < x) {small->next = pcur;small = small->next;} else {big->next = pcur;big = big->next;}pcur = pcur->next;}// 連接兩個鏈表big->next = nullptr; // 防止循環鏈表small->next = bigDummy->next;ListNode* result = smallDummy->next;delete smallDummy;delete bigDummy;return result;}