联系
Knight's Blog » 工作

逆置单链表,求单链表中间元素,删除指定结点

2009-09-25 21:03

本程序实现单链表的一些稍微高级一点的操作: <ul> <li>查找单链表倒数第n个元素的值</li> <li>查找单链表中间元素的值(中间值可能有两个)</li> <li>一个单向的链表,知道只有一个指向某个节点的指针p,并且假设这个节点不是尾节点,试编程实现删除此节点</li> </ul> 具体算法是:

4、在查找单链表倒数第n个元素时,有三种方法 第一种是规尺法,即利用两个步长为n的指针,同时前进直至第一个指针到达终点,那么第二个指针所指的对象就是想要得到的值,时间复杂度为O(2N),空间复杂度为0 第二种是构造一个先进先出队列(指针队列),大小为n,遍历单链表,将遍历到的单链表结点的地址逐个存进队列中,直至单链表遍历结束.那么,这个队列的最后一个元素就是想要得到的数据,时间复杂度为O(N),空间复杂度为O(n) 第三种方法可以先逆置该链表,然后顺序取第n个元素作为结果返回,最后再次逆置链表时间复杂度为O(3N),空间复杂度为0

5、用最快的方法求出单链表中间的元素 用二个指针,一开始同时指向链表头,然后同时往后走,第一个指针走二步,第二个指针走一步,那么,当第一个指针走到头时,第二个指针所指向的就是需要返回的值。当单链表元素个数为单数,中间元素值其实是有二个.可以通过这样来判断:当第一个指针走二步刚好是NULL,则说明单链表有偶数个元素,则应该返回二个中间值当第一个指针走一步刚才是NULL,则说明单链表有奇数个元素,则应该返回一个中间值。

<!--more-->6、一个单向的链表,知道只有一个指向某个节点的指针p,并且假设这个节点不是尾节点, 试编程实现删除此节点. 此问题,可以将p下面的那个结点的值赋给p,然后将p的next指针指向下下个结点就可以了. 如: 5-&gt;4-&gt;3-&gt;2-&gt;1 要删除4这个结点,那么,我们就将3赋给4,变成了 5,3,3,2,1 然后改变指针的指向, 变成 5,3,[3],2,1 (中括号的表示被删除掉)

程序清单:

<!--more--> <pre class="brush:cpp; ruler:true">//--------------------------------------------------------------------------- // KnightList::FindInverseElemSingleList // // 寻找倒数第n个元素 int KnightList::FindInverseElemSingleList(int n,int type) { switch(type){

    // 第一种方法,用标迟法
    case 1:
        {
            struct KnightNode*p,*q;
            p = q = m_singleList-&amp;gt;next;
            int tmpN = n;

            while(1){
                if(!tmpN)
                    break;
                if(p==NULL)
                    break;
                p = p-&amp;gt;next;
                --tmpN;
            }

            if(tmpN&amp;gt;0)
                return -99999;  // 没有找到

            while(p){
                p = p-&amp;gt;next;
                q = q-&amp;gt;next;
            }

            return q-&amp;gt;value;
        }
        break;

    // 用先进先出指针队列实现
    case 2:
        {
            struct KnightNode** pArray;
            // 开辟的是指针数组
            pArray = new (KnightNode*[n]);
            int found = false;

            struct KnightNode* p = m_singleList-&amp;gt;next;
            int i=0;
            while(p){
                pArray[i] = p;
                p = p-&amp;gt;next;

                // 这里有个问题
                // 不可写成
                /*
                    if(i&amp;gt;=n){
                        i=0;
                        found = true;
                    }
                    else{
                        ++i;
                    }
                    我们一定要先让i先加起来,再判断这时的i是否有越界
                    这里很容易出错
                */
                ++i;
                if(i&amp;gt;=n){
                    i = 0;
                    found = true;
                }
            }

            if(!found){
                // 注意 指针数组需要释放
                delete []pArray;
                return -9999;
            }

            int ret = (*pArray[(i)%n]).value;
            delete []pArray;

            return ret;
        }
        break;

    case 3:
        {
            ConverseSingleList();

            struct KnightNode* p = m_singleList-&amp;gt;next;

            int tmpN = n;
            while(p){
                p = p-&amp;gt;next;
                --tmpN;

                // 要减到1,而不是0
                /*
                    这里
                    if(tmpN==0)
                        break; 是错的
                */
                if(tmpN==1)
                    break;
            }

            if(tmpN&amp;gt;1)
                return -9999;

            int ret = p-&amp;gt;value;

            ConverseSingleList();

            return ret;
        }
        break;
}

return -99999;

}

//--------------------------------------------------------------------------- // KnightList::FindMiddleSingleList // // 寻找中间元素 // ret1 和 ret2是返回的两个中间值 // 本函数返回的值是: 有几个中间值 int KnightList::FindMiddleSingleList(int &amp;ret1,int &amp;ret2) { struct KnightNode p,q; p = q = m_singleList-&gt;next;

int step = 0;

while(1){

    // 第一个指针走
    p = p-&amp;gt;next;
    step= (step+1)%2;   // 记录第一个指针最后一次到底是走几步才NULL
    if(NULL==p)
        break;
    p = p-&amp;gt;next;
    step= (step+1)%2;
    if(NULL==p)
        break;

    // 第二个指针走
    q = q-&amp;gt;next;
}

ret1 = q-&amp;gt;value;
if(step==1){
    // 一个中间值
    return 1;
}
ret2 = (q-&amp;gt;next)-&amp;gt;value;
return 2;

}

//--------------------------------------------------------------------------- // KnightList::DeleteNodeSingleList // // 删除指定的结点 void KnightList::DeleteNodeSingleList(void *node) { if(NULL==node) return;

struct KnightNode* p = (struct KnightNode*)node;

// 将该元素的值赋为下个元素的值
p-&amp;gt;value = p-&amp;gt;next-&amp;gt;value;
// 然后将该指针指向下下的元素
p-&amp;gt;next = p-&amp;gt;next-&amp;gt;next;

}</pre>

1749 次点击