// 單鏈表
struct ListNode {int val;  // 節(jié)點(diǎn)上存儲(chǔ)的元素ListNode *next;  // 指向下一個(gè)節(jié)點(diǎn)的指針ListNode(int x) : val(x), next(NULL) {}  // 節(jié)點(diǎn)的構(gòu)造函數(shù)
};ListNode* head = new ListNode(5);

重要方法：虛擬頭節(jié)點(diǎn)?

個(gè)人方法：指針轉(zhuǎn)為數(shù)組（詳見(jiàn)4、5）

1.移除鏈表元素

203. 移除鏈表元素 - 力扣（LeetCode）
方法一：

ListNode* removeElements(ListNode* head, int val) {// 刪除頭結(jié)點(diǎn)while (head != NULL && head->val == val) { // 注意這里不是ifListNode* tmp = head;head = head->next;delete tmp;}// 刪除非頭結(jié)點(diǎn)ListNode* cur = head;while (cur != NULL && cur->next!= NULL) {if (cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;} else {cur = cur->next;}}return head;
}

方法二（虛擬頭節(jié)點(diǎn)）：

ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0); // 設(shè)置一個(gè)虛擬頭結(jié)點(diǎn)dummyHead->next = head; // 將虛擬頭結(jié)點(diǎn)指向head，這樣方便后面做刪除操作ListNode* cur = dummyHead;while (cur->next != NULL) {if(cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;} else {cur = cur->next;}}head = dummyHead->next;delete dummyHead;return head;
}

2.設(shè)計(jì)鏈表

707. 設(shè)計(jì)鏈表 - 力扣（LeetCode）

3.反轉(zhuǎn)鏈表

206. 反轉(zhuǎn)鏈表 - 力扣（LeetCode）

ListNode* reverseList(ListNode* head) {ListNode* dummy = new ListNode();ListNode* cur;while(head != nullptr){cur = head;head = head->next;cur->next = dummy->next;dummy->next = cur;}return dummy->next;
}

4.鏈表相交

面試題 02.07. 鏈表相交 - 力扣（LeetCode）

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 轉(zhuǎn)化為指針數(shù)組vector<ListNode*> a, b;while(headA != NULL){a.push_back(headA);headA = headA->next;}while(headB != NULL){b.push_back(headB);headB = headB->next;}int mini = min(a.size(), b.size());ListNode* res = NULL;for(int i = 1; i <= mini; i ++){if(a[a.size() - i] == b[b.size() - i]) res = a[a.size() - i];}return res;
}

?5.環(huán)形鏈表

142. 環(huán)形鏈表 II - 力扣（LeetCode）

方法一：暴力

ListNode *detectCycle(ListNode *head) {vector<ListNode*> array;ListNode* res = NULL;while(head != NULL){for(int i = 0; i < array.size(); i ++ ){if(array[i] == head) return head;}array.push_back(head);head = head->next;}return res;
}

方法二：雙指針

ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;// 快慢指針相遇，此時(shí)從head 和 相遇點(diǎn)，同時(shí)查找直至相遇if (slow == fast) {ListNode* index1 = fast;ListNode* index2 = head;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index2; // 返回環(huán)的入口}}return NULL;
}