数据结构之链表与数组（二）－单向链表上的简单操作问题


		  本文主要介绍一些解决单向链表上部分操作问题的思路和代码实现。
      主要的问题包括以下几点：
            1 向单向链表中插入一个节点
            2 删除单向链表中的一个节点
            3 查找单向链表中的一个节点
                  扩展问题1：查找单向链表中的倒数第k个节点。
                  扩展问题2：查找单向链表中的中间节点，当节点总个数为偶数时返回中间两个元素中的前者（后者）
      4反转单向链表（非递归实现）
      5反转单向链表（递归实现）
      6判断单向链表是否有环
      7判断两个单向链表是否相交
            扩展问题：返回两个链表的第一个交点。
      8 用单链表实现栈，要求push和pop的时间复杂度为O（1）
      9 用单链表实现队列，要求enQueue和deQueue的时间复杂度为O（1）
      10 在一个链表中删除另一个链表中的元素（即求差集（A－B））
      由html">上一篇文章可知，从数据的底层存储角度来讲，数据结构可分顺序表（数组）和链表两种。因此，要掌握好数据结构，首先就要掌握好对数组和链表的操作。
      在本篇文章中，主要先介绍一些链表的基本操作。
一个链表又可以有好多种表现形式，它可以是单向的或双向的，也可以是排序的或者未排序，或者是环形的和非环形的。下面主要介绍一些链表的常见的操作。
      在解决生活或计算机中的任何问题时“三思而后行”的道理都是非常实用的。只有想明白了，要做什么、怎么做，然后再着手去做，才能比较容易地解决问题。如果连要做什么，怎么做都不清楚，那现在所做的行动能成功的概论就非常小了。因此，要用计算机编码来解决一些问题的时候，不要急于编码，而是要先想清楚思路和注意点，然后再着手实现自己的思路。
      在处理链表问题时的公共注意点有：
         1，要时刻考虑指针是否为空
         2，不要把指针指向一些无效的地址空间。
         3，如果没要求，操作的过程中尽量不要破坏链表的原始结构；如果破坏链表的结构是目前较好的一种实现方式，那么处理完数据后，一定要记得还原链表的原始数据结构。
      下面介绍一些常见的单向链表上的操作问题。
单向链表节点定义：
class SingleList
//单向链表上的节点定义
class SingleList
{
public:
    int data;
    SingleList *next;   //指向下一个结点的指针

    SingleList()
    {
        next = NULL;
    }
};
      1 向单向链表中插入一个节点
思路：如图1所示，向链表中插入一个节点。

图1  插入节点
      如果已知一个节点指针pre和一个节点指针cur，要把cur插入到pre节点之后，很显然要保证链表不会断开而丢失后面的节点，要先把后面的节点指针（指向lat的指针）保存下来，即有cur->next = pre->next，然后把cur连接的一串链表连接到pre后面，即pre->next = cur;
上面介绍了，在一个节点之后插入节点的情况。这是通常的情况。如果要向一个链表的头部插入节点，就只需要将新节点的下一个指针指向链表的头指针即可。
      在这种情况下，有两点要注意：
            1，链表是否为空链表
            2，要插入的节点是不是空指针。
代码实现：
//向单链表中插入一个节点(插入在链开始处)
//输入参数：单链表的头指针和要插入的节点指针
//输出参数：无
//返回值：指向单链表的头指针
SingleList* Insert(SingleList *head,SingleList *node)
{
    if(node == NULL)
    {
        return head;
    }
    else if(head == NULL)
    {
        return node;
    }

    node->next = head;
    head = node;
    return head;
}
      2 删除单向链表中的一个节点
思路：

图2  删除节点cur
      如图2所示，要删除节点cur就像要在环环相扣的链上去掉一环一样, 我们只需要将前面的环和当前环所连接的下一个环相连就可以了。
针对这情况，我只需要从头遍历链表，找到当前节点的前一节点pre,然后令pre->next = cur->next。因为要从头遍历链表所以删除操作的时候时间复杂度是O（n）。
      但是，在有些情况下，如果要求时间复杂度必须为O（1），我们又能怎么做呢？想一下，如果要求时间复杂度为O（1）的话，肯定不能再遍历链表，而是在当地做几个小步聚，那么做什么才能删除呢？
      如果不能找到cur的前一个节点,那我们是不是可以像数组中的覆盖一样用后一个节点的值把当前节点值覆盖，然后删除后一个节点呢。当然可以，如图3所示。但是，这种方法存在一个局限，就是如果要删除的节点是尾节点的话，即没有可以替代它被删除的点时，我们就只能按上面的循环遍历查找前一个节点了。

图3  删除节点cur（不知道头指针时）
      在删除链表中的节点时，要特别注意链表的头节点和尾节点。
代码实现：
SingleList* Delete(SingleList *head,SingleList *node)
//在单链表中删除一个节点
//输入参数：单链表的头指针和要删除的节点
//输出参数：无
//返回值：指链表的头指针
SingleList* Delete(SingleList *head,SingleList *node)
{
    SingleList *pSL;
    
    //链表为空或要删除的结点为空
    if((head == NULL)||(node == NULL))
    {
        return head;
    }

    //如果删除的不是尾节点
    if(node->next != NULL)
    {
        pSL = node->next;
        node->next = node->next->next;
        node->data = pSL->data;

        delete pSL;
        pSL = NULL;

        return head;
    }
    //如果删除的是尾节点
    else
    {
        pSL = head;

        while((pSL->next != NULL)&&(pSL->next != node))
        {
            pSL = pSL->next;
        }
        if(pSL->next != NULL)
        {
            pSL->next = pSL->next->next;
            delete node;
        }
        return head;
    }
}
      3 查找单向链表中的一个节点
思路：
      这个问题比较简单，只需要在从头一步一步的逐个判断节点值是不是要找的值就可以了。
代码实现：
数据结构之链表与数组（二） －单向链表上的简单操作问题

数据结构之链表与数组（二）－单向链表上的简单操作问题
