跳转至

移除链表元素 & 设计链表 & 反转链表

约 112 个字 53 行代码 预计阅读时间 1 分钟

Abstract

掌握画图进行分析以及常见的题型方法

链表的定义: 

1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
}

203.移除链表元素

  1. 两种情况: case1删除的是头，case2删除的非头 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    ListNode* removeElements(ListNode* head, int val) {
    // case1
    while (head != nullptr && head->val == val) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
    // case2
    ListNode* cur = head;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    return head;
}
  2. 利用 虚拟头节点dummy 统一操作 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = dummy;
    while (cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    head = dummy->next;
    delete dummy;
    return head;
}

707.设计链表

单链表的增删

利用虚拟头节点 → Ref

206.反转链表

每次维护相邻的指针，完成反向，继续向后走 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;s
    ListNode* pre = nullptr, *cur = head;
    while(cur) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论