天水建设银行网站,青海公路建设信息服务网站,小网站搜什么关键词,网站建设交流材料目录 一、移除链表元素二、设计链表三、反转链表四、两两交换链表中的节点五、删除链表倒数第N个节点六、链表相交七、环形链表Ⅱ 一、移除链表元素
Leetcode 203
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead new Lis… 目录 一、移除链表元素二、设计链表三、反转链表四、两两交换链表中的节点五、删除链表倒数第N个节点六、链表相交七、环形链表Ⅱ 一、移除链表元素
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;stackListNode* 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;}
};
