203、移除鏈表元素

不帶頭節點

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {while(head != NULL && head->val == val) {ListNode* tem = head;head = head->next;delete tem;}ListNode* cur = head;while(cur != NULL && cur->next != NULL) {if(cur->next->val == val) {ListNode* tem = cur->next;cur->next = tem -> next;delete tem;}else {cur = cur->next; }}return head;}
};

時間復雜度：O(n)

空間復雜度：O(1)

帶頭節點

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

時間復雜度：O(n)

空間復雜度：O(1)

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 <= -1 || index >= size) {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 != NULL) {cur = cur->next;}cur->next = newNode;size++;}void addAtIndex(int index, int val) {if(index <= -1 || index > size) {return;}size++;if(index == size) {addAtTail(val);return;}LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;}void deleteAtIndex(int index) {if(index <= -1 || index >= size) {return ;}LinkedNode* cur = dummyHead;while(index--) {cur = cur->next;}LinkedNode* tem = cur->next;cur->next = tem->next;delete tem;size--;}private: LinkedNode* dummyHead;int size;
};

206、反轉鏈表

雙指針：

用cur指針遍歷舊鏈表，head指針指向新鏈表的第一個結點，用tem指針取出遍歷到的結點，將其指向head作為新鏈表的第一個節點，更新head。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;head = NULL;ListNode* tem = NULL;while(cur != NULL) {tem = cur;cur = cur->next;tem-> next = head;head = tem;}return head;}
};

時間復雜度：O(n)

空間復雜度：O(1)