首页 » 开发 » 链表

单向列表

单向列表的每个节点只存储一个next指针,指向下一个元素:

struct node
{
    node(int d = 0, node* n = NULL) 
        : _data(d), _next(n) {}

    int _data;
    node* _next;
};

在链表中有一个head指针指向第一个节点,为了加入元素方便,可以另设置一个tail指针,指向最后一个节点:

class slist
{
    public:
        slist() : _header(NULL), _tail(NULL) {}

     public:
        node* _header;
        node* _tail;
};

单向链表的反转操作:

void slist::reverse()
{
    // not initialized or just one node
    if(_header == _tail) return;

    node* p = _header;
    node* pnext = p->_next;
    node* ptmp = NULL;

    while(p and pnext) {
        ptmp = pnext->_next;
        pnext->_next = p;
        p = pnext;
        pnext = ptmp;
    }

    _tail = _header;
    _tail->_next = NULL;
    _header = p;
}

关于单向列表常见的几个问题:

  • 判断一个链表是否有环?如果链表有环,找出入口。
  • 判断两个单向链表是否相交,若相交则找出交点。

单向链表是否有环的几种常见解决方案:

  • 遍历链表,并把经过的每个节点地址保存在一个hash表中,每走一个节点,查找hash表中是否存在。这个方案需要O(N)个额外空间,每次查找节点是否存在时间复杂度为O(1),总体时间复杂度为O(N)。
  • 反转链表。
  • 快慢指针。

分享

0