单链表 知识点学习--Android地基系列(一)

嗯,看别人整理过,自己再做的笔记,题目都是常见的必考题目,嘻嘻嘻,单链


表的基础知识我就不写了,太多人写了。




看前注意!!!!!!!涉及C知识较多,C知识我以后再考虑是否写一篇附加文


可以辅助以后的Android必备地基系列博文


struct ListNode
{
    int data;
    ListNode * Next;

}; 




1、求链表中结点个数
思路:若链表为空,返回0;循环判断链表下一个指针是否为空,no,长度++(初始化用unsigned int  length = 0),直到下一个为null,返回长度


// 求单链表中结点的个数  
unsigned int GetListLength(ListNode * pHead)  
{  
 if(pHead == NULL)  
  return 0;  
  
 unsigned int mLength = 0;  
 ListNode * pCurrent = pHead;  
 while(pCurrent != NULL)  
 {  
  mLength ++;  
  pCurrent = pCurrent->m_pNext;  
 }  
 return mLength ;  
}  

2、将单链表反转
思路:从头到尾遍历原链表,每遍历一个结点,将其摘下放在新链表的最前端。


注意链表为空和只有一个结点的情况。时间复杂度为O(n); (这是方法2)
如何把一个单链表进行反转?
方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。
方法2:使用3个指针遍历单链表,逐个链接点进行反转。
方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后


,最后将第一个节点挪到新表的表尾。
方法4:   递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑


用递归来解决。但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使


用递归。可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归


来解决。或者说,因为单链表本身的结构也有自相似的特点,所以可以考虑用递


归来解决)
http://blog.csdn.net/feliciafay/article/details/6841115


贴上代码,

ListNode* ReverseList(ListNode* head)  
{  
  
 if(NULL==head|| NULL==head->next)   
      return head;    //少于两个节点没有反转的必要。  
 ListNode* p = head;  
 ListNode* q = head->next;  
 ListNode* r;  
    head->next = NULL;        //旧的头指针是新的尾指针,next需要指向

NULL  
    while(q){  
        r = q->next; //先保留下一个step要处理的指针  
        q->next = p; //然后p q交替工作进行反向  
        p = q;   
        q = r;   
    }  
 head=p; // 最后q必然指向NULL,所以返回了p作为新的头指针  
    return head;      
}  

3、查找单链表中的倒数第K个结点
最普遍的方法是,先统计单链表中结点的个数,然后再找到第(n-k)个结点。注


意链表为空,k为0,k为1,k大于链表中节点个数时的情况。时间复杂度为O(n)


。代码略。
这里主要讲一下另一个思路,这种思路在其他题目中也会有应用。
主要思路就是使用两个指针,先让前面的指针走到正向第k个结点,这样前后两个


指针的距离差是k-1,之后前后两个指针一起向前走,前面的指针走到最后一个结


点时,后面指针所指结点就是倒数第k个结点。




实际题型
已知一个带有表头结点的单链表,结点结构为


假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高


效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算


法输出该结点的 data域的值,并返回1;否则,只返回0。要求:
1)描述算法的基本设计思想。
2)描述算法的详细实现步骤。
3)根据设计思想和实现步骤,釆用程序设计语言描述算法(使用C、C++或Java语


言实现),关键之处请给出简要注释。
问题解答:
1)算法的基本设计思想如下:(思想其实就是上上边的另一个思路)
问题的关键是设计一个尽可能高效的算法,通过链表的一趟遍历,找到倒数第k个


结点的位置。算法的基本设计思想是:定义两个指针变量p和q,初始时均指向头结


点的下一个结点(链表的第一个结点),p指针沿链表移动;当p指针移动到第k个


结点时,q指针开始与P指针同步移动
;当p指针移动到最后一个结点时,q指针所指示结点为倒数第k个结点。以上过程


对链表仅进行一遍扫描。




2)算法的详细实现步骤如下:
①count=0,p和q指向链表表头结点的下一个结点。
②若p为空,转⑤。
③若count等于k,则q指向下一个结点;否则,count=count+1。
④p指向下一个结点,转②。
⑤若count等于k,则查找成功,输出该结点的data域的值,返回1;否则,说明k


值超过了线性表的长度,查找失败,返回0。(查k的值)
⑥算法结束。


3)算法实现
typedef int ElemType;    //链表数据的类型定义
typedef struct LNode{    //链表结点的结构定义
    ElemType data;        //结点数据
    struct Lnode *link;    //结点链接指针
}LNode, *LinkList;        //c知识,忘了可以回去查


int Search_k(LinkList list,int k) {  
    //查找链表list倒数第k个结点,并输出该结点data域的值  
    LNode *p = list->link, *q=list->link;  //指计;p、q 指示第一个结点  
    int count=0;  
    while (p!=NULL) {  //遍历链表直到最后一个结点  
        if (count<k) count++;  //计数,若 count<k 只移动 p  
        else q=q->link;  
        p-p->link;  //之后让p、q同步移动  
    } //while  
    if(count<k)  
        return 0;  //查找失败返回0  
    else{    //否则打印并返回1  
    printf("%d", q->data);  
    return 1;  
    }  
} //Search_k  



//先到这吧 2015-2-27  脑瓜子感觉又要扩容了 ,还有8个单链表的知识,待我好好消化,以后不定期分享~欢迎关注(*^__^*)  GarryLin~

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。