第二章 链表

一、移除链表元素

Leetcode 203

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while (cur->next != nullptr) {if (cur->next->val == val) {ListNode* tmp = cur->next;cur->next = tmp->next;delete tmp;} else cur = cur->next;}head = dummyHead->next;delete dummyHead;return head;}
};

二、设计链表

Leetcode 707

class MyLinkedList {
public:struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val): val(val), next(nullptr) {}};MyLinkedList() {_dummyHead = new LinkedNode(0);_size = 0;}int get(int index) {if (index > (_size - 1) || index < 0) return -1;LinkedNode* cur = _dummyHead->next;while (index -- ) cur = cur->next;return cur->val;}void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size ++ ;}void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while (cur->next != nullptr) cur = cur->next;cur->next = newNode;newNode->next = nullptr;_size ++ ;}void addAtIndex(int index, int val) {if (index > _size) return;if (index < 0) index = 0;LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while (index -- ) cur = cur->next;newNode->next = cur->next;cur->next = newNode;_size ++ ;}void deleteAtIndex(int index) {if (index >= _size || index < 0) return;LinkedNode* cur = _dummyHead;while (index -- ) cur = cur->next;LinkedNode* tmp = cur->next;cur->next = tmp->next;delete(tmp);_size -- ;}private:int _size;LinkedNode* _dummyHead;
};

三、反转链表

Leetcode 206

双指针法：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *tmp, *cur = head, *pre = nullptr;while (cur) {tmp = cur->next;cur->next = pre;pre = cur, cur = tmp;}return pre;}
};

递归法：

class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur) {if (cur == nullptr) return pre;ListNode* tmp = cur->next;cur->next = pre;return reverse(cur, tmp);}ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}
};

头插法：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* dummy = new ListNode(-1);dummy->next = nullptr;ListNode* cur = head;while (cur != nullptr) {ListNode* tmp = cur->next;cur->next = dummy->next;dummy->next = cur;cur = tmp;}return dummy->next;}
};

使用栈来反转链表：

class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr) return nullptr;if (head->next == nullptr) return head;stack<ListNode*> stk;ListNode* cur = head;while (cur != nullptr) stk.push(cur), cur = cur->next;ListNode* dummy = new ListNode(-1);cur = dummy;while (!stk.empty()) {ListNode *node = stk.top(); stk.pop();cur->next = node;cur = cur->next;}cur->next = nullptr;return dummy->next;}
};

四、两两交换链表中的节点

Leetcode 24

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummy = new ListNode(-1);dummy->next = head;ListNode* cur = dummy;while (cur->next != nullptr && cur->next->next != nullptr) {ListNode* tmp = cur->next->next->next;ListNode* tmp1 = cur->next;cur->next = cur->next->next;cur->next->next = tmp1;cur->next->next->next = tmp;cur = cur->next->next;}return dummy->next;}
};

五、删除链表倒数第N个节点

Leetcode 19

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(-1);dummy->next = head;ListNode *slow = dummy, *fast = dummy;while (n -- && fast != nullptr) fast = fast->next;fast = fast->next; // fast 多走一步，last少走一步到被删除节点的前一个节点，方便删除while (fast != nullptr) fast = fast->next, slow = slow->next;ListNode* tmp = slow->next;slow->next = tmp->next;delete(tmp);return dummy->next;}
};

六、链表相交

面试题 02.07

双指针：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) return nullptr;ListNode *pa = headA, *pb = headB;while (pa != pb) {pa = pa == nullptr ? headB : pa->next;pb = pb == nullptr ? headA : pb->next;}return pa;}
};

先统计两个链表长度，再将较长链表先遍历到两个链表能尾部对其的位置，再开始遍历。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *curA = headA, *curB = headB;int lenA = 0, lenB = 0;while (curA != nullptr) curA = curA->next, lenA ++ ;while (curB != nullptr) curB = curB->next, lenB ++ ;curA = headA, curB = headB;if (lenB > lenA) swap(lenA, lenB), swap(curA, curB);int gap = lenA - lenB;while (gap -- ) curA = curA->next;while (curA != nullptr) {if (curA == curB) return curA;curA = curA->next;curB = curB->next;}return nullptr;}
};

七、环形链表Ⅱ

Leetcode 142

参考题解

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head, *slow = head;while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;if (fast == slow) {ListNode *p1 = fast, *p2 = head;while (p1 != p2) p1 = p1->next, p2 = p2->next;return p1;}}return nullptr;}
};