算法刷题之链表

// 单链表
struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};ListNode* head = new ListNode(5);

重要方法：虚拟头节点 

个人方法：指针转为数组（详见4、5）

1.移除链表元素

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

ListNode* removeElements(ListNode* head, int val) {// 删除头结点while (head != NULL && head->val == val) { // 注意这里不是ifListNode* tmp = head;head = head->next;delete tmp;}// 删除非头结点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;
}

方法二（虚拟头节点）：

ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点dummyHead->next = head; // 将虚拟头结点指向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.设计链表

707. 设计链表 - 力扣（LeetCode）

3.反转链表

206. 反转链表 - 力扣（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) {// 转化为指针数组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.环形链表

142. 环形链表 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;// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇if (slow == fast) {ListNode* index1 = fast;ListNode* index2 = head;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index2; // 返回环的入口}}return NULL;
}