19. 删除链表的倒数第 N 个结点
- 19. 删除链表的倒数第 N 个结点
- 思路:注释中
- 时间:O(n);空间:O(1)
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy_head = new ListNode(-1, head);ListNode* fast = dummy_head->next, *slow = dummy_head;for(int i = 0; i < n; i++){fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummy_head->next;}
};
160. 相交链表
- 160. 相交链表
- 思路:注释中
- 时间:O(n + m);空间:O(1)
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p = headA, *q = headB;int len_a = 0, len_b = 0;while(p){len_a++;p = p->next;}while(q){len_b++;q = q->next;}p = headA, q = headB;while(len_a > len_b){len_a--;p = p->next;}while(len_b > len_a){len_b--;q = q->next;}while(q && p){if(q == p){return p;} else {q = q->next;p = p->next;}}return nullptr;}
};
83. 删除排序链表中的重复元素
- 83. 删除排序链表中的重复元素
- 思路:链表
- 时间:O(n);空间:O(1)
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head == nullptr) return nullptr;ListNode *p = head, *q = head->next;while(p && q){if(p->val == q->val){q = q->next;p->next = q;} else {p = q;q = q->next;}}return head;}
};
203. 移除链表元素
- 203. 移除链表元素
- 时间:O(n);空间:O(1)
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {if(head == nullptr) return nullptr;ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head, *q = dummy_head->next;while(q){if(q->val == val){p->next = q->next;q = q->next;} else {p = q;q = q->next;}}return dummy_head->next;}
};