C++数据结构与算法之单向链表


如果一个节点将指向另一个节点的指针作为数据成员,那么多个这样的节点可以连接起来,只用一个变量就能够访问整个节点序列。这样的节点序列就是最常用的链表实现方法。 链表是一种由节点组成的数据结构,每个节点都包含某些信息以及指向链表中另一个节点的指针。如果序列中的节点只包含指向后继节点的链接,该链表就成为单向链表。

屏幕快照 20191122 上午10.40.43.png

下图是调试的截图,可以看出,链表的存储就相当于一个链,通过next串联起来 单向链表

文中涉及代码

intSLList.h

#ifndef STRUCTURE_INTSLLIST_H
#define STRUCTURE_INTSLLIST_H

class IntSLLNode {
public:
    IntSLLNode() {
        next = 0;
    }

    IntSLLNode(int el, IntSLLNode *ptr = 0) {
        info = el;
        next = ptr;
    }

    int info;
    IntSLLNode *next;
};

class IntSLList {
public:
    IntSLList() {
        head = tail = 0;
    }

    ~IntSLList();

    int isEmpty() {
        return head == 0;
    }

    void addToHead(int);

    void addToTail(int);

    int deleteFromHead();

    int deleteFromTail();

    void deleteNode(int);

    bool isInList(int) const;

private:
    IntSLLNode *head, *tail;
};


#endif //STRUCTURE_INTSLLIST_H

intSLList.cpp

#include <iostream>
#include "intSLList.h"

IntSLList::~IntSLList() {
    for (IntSLLNode *p; !isEmpty();) {
        p = head->next;
        delete head;
        head = p;
    }
}

void IntSLList::addToHead(int el) {
    head = new IntSLLNode(el, head);
    if (tail == 0)
        tail = head;
}

void IntSLList::addToTail(int el) {
    if (tail != 0) {
        tail->next = new IntSLLNode(el);
        tail = tail->next;
    } else
        head = tail = new IntSLLNode(el);
}

int IntSLList::deleteFromHead() {
    int el = head->info;
    IntSLLNode *tmp = head;
    if (head == tail) {
        head = tail = 0;
    } else {
        head = head->next;
    }
    delete tmp;
    return el;
}

int IntSLList::deleteFromTail() {
    //tail节点内容
    int el = tail->info;
    if (head == tail) {
        delete head;
        head = tail = 0;
    } else {
        IntSLLNode *tmp;
        //找到tail的前驱,把它设置为尾节点,才能删除掉之前的尾节点
        for (tmp = head; tmp->next != tail; tmp = tmp->next);
        delete tail;
        tail = tmp;
        //注意设置新tail后驱为null
        tail->next = 0;
    }
    return el;
}

void IntSLList::deleteNode(int el) {
    if (head != 0) {
        if (head == tail && el == head->info) {
            delete head;
            head = tail = 0;
        } else if (el == head->info) {//如果链表多于一个节点,并且头节点为所要查找的元素
            IntSLLNode *tmp = head;
            head = head->next;
            delete tmp;
        } else {
            //单链表pred,记录前节点,用来做删除,可以链接到后面一个节点
            IntSLLNode *pred, *tmp;
            for (pred = head, tmp = head->next;
                 tmp != 0 && tmp->info != el;//tmp不是tail,并且是所查找的元素
                 pred = pred->next, tmp = tmp->next //pred和tmp又向后移动
                    );
            //如果现在的tmp不是指向null,注意在找到元素的时候,tmp又会后移了一次,见for循环
            if (tmp != 0) {
                pred->next = tmp->next;
                if (tmp == tail) //现在tmp指针指向的地址和tail的地址一致
                    tail = pred;//
                delete tmp;
            }
        };
    }
}

bool IntSLList::isInList(int el) const {
    IntSLLNode *tmp;
    for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);
    return tmp != 0;
}



力扣有个单链表的习题可以练习下:

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807

官方题解:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //将当前节点初始化为返回列表的哑节点
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    //最后一位相加,注意进位问题
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
   //去掉哑节点后输出
    return dummyHead.next;
}

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-two-numbers

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×