Linked Lists 第二课时

引用传递：

在编写添加函数的时候我们会遇到一个问题

void addFront(ListNode* front, int value){
    ListNode* temp = new ListNode(value);
    temp->next = front;
    front = temp;
}

你会发现,这段代码没有任何作用;

这是因为这段代码用的是值传递;

值传递的本质是:

1. 拷贝函数参数的副本
2. 对副本进行修改
3. 原参数不受影响

因此我们需要使用引用传递:

void addFront(ListNode*& front, int value){
    ListNode* temp = new ListNode(value);
    temp->next = front;
    front = temp;
}

没错,我们在函数声明中添加了一个引用符号&,这意味着我们传递的是引用而不是副本.

况且,引用传递更加快速和灵活,因为它可以直接修改原参数,而不需要拷贝副本.

在结尾处添加元素

根据思路我们写出了第一版代码:

void add(ListNode*& front, int value) {
    ListNode* current = front;
    while (current->next != nullptr) {
        current = current->next;
    }

    // current points to the last node
    ListNode* newNode = new ListNode(value);
    newNode->next = nullptr;
    current->next = newNode;
}

此时你会发现,这段代码会报错:

大致长这样

这是因为:执行过程中尝试解引用了一个为 NULL 或无效的指针,这段函数并不适用于链表为空的时候.

所以

指针是由为危险的!!!!!!!!!!!!!!!!!!!

那么我们如何解决他呢?

解决方法:

我们可以先判断链表是否为空,如果为空,我们直接创建一个新的节点,然后将其作为链表的头节点.

void add(ListNode*& front, int value) {
    if (front == nullptr) {
        // empty list
        front = new ListNode(value);
    } else {
        // non-empty list; general case
        ListNode* current = front;
        while (current->next != nullptr) {
            current = current->next;
        }
        // current points to the last node
        ListNode* newNode = new ListNode(value);
        newNode->next = nullptr;
        current->next = newNode;
    }
}

这种模板可以用于几乎任何链表的问题

Fristremove(删除第一个)

删除数据如果处理的不到位,那么就会造成内存泄漏

所以我们需要delete掉要删除的节点

然后我们就需要考虑各种情况:

1. 链表是否存在
2. 链表是否有第二个 node

....