江苏龙网

  1. 主页 > 生活百科 > >

关于链表的理解( 三 )

链表


                p=p->next;
            }
        }
    }
    return head; 
     
} 
链表的遍历
 
void printList(struct ListNode *head)
{
    struct ListNode *p=head;//p依然为辅助指针
    while(p!=NULL)//因为是遍历（打印输出）操作 所以对当前节点进行操作即可 
    {
       printf("%d",p->val);
       p=p->next; 
    } 
}
 
双向链表
双向链表即单链表由单向的链变成了双向的链（一个指针域(next)变成一前一后两个指针域(prev,next)） 这里只演示双向链表的创建
另：
节点结构为：
 
struct ListNode
{
int val;
ListNode *prev;
ListNode *next;
};
 
双向链表的创建 
struct ListNode *createDbList()
{
    struct ListNode*p=NULL,*head=NULL,*tail=NULL;
    int num;
    scanf("%d",&num);
    while(num!=-1)//以-1作为创建链表结束的标志 
    {
        p=(struct ListNode*)malloc(sizeof(struct ListNode));
        p->val=num;
        if(head==NULL)//这里主要演示尾插法 
        {
           head=p;    
【关于链表的理解】           p->prev=NULL; //就不将双向链表和循环链表相互掺和了 
        } 
        else
        {
          tail->next=p;
          p->prev=tail;     
        }
        tail=p;
    } 
    tail->next=NULL;
}
 
循环链表
即将链表首尾相接 同样这里只演示循环链表的创建
 
struct ListNode *createList()
{
    struct ListNode*p,*head,*tail;
    int num;
    scanf("%d",&num);
    while(num!=-1)
    {
       p=(struct ListNode*)malloc(sizeof(struct ListNode));
       p->val=num;
       if(head==NULL)
       {
          head=p;    
       }    
       else
       {
             tail->next=p;
       }
       tail=p;
    }
    tail->next=head;//创建结束后将链表首尾相接    
} 
 
静态链表
静态链表的节点通常用结构体数组表示
 
struct  staticListNode
{ 
   int val;
   int cur;//游标cur用来储存后继节点的下标
};
 
 
1.Floyd判圈法：判断链表是否有环（快慢指针的应用）
 
 
对于链表找环路的问题，有一个通用的解法——快慢指针(Floyd)。给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头 。每次 fast 前进两步，slow 前进一步 。如果 fast 可以走到尽头，那么说明没有环路；如果fast 可以无限走下去，那么说明一定有环路，且一定存 在一个时刻 slow 和 fast 相遇 。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并 让 slow 和 fast 每次都前进一步 。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点 。
 
2. 判断两个链表是否相交
 
 
假设链表 A 的头节点到相交点的距离是 a，链表 B 的头节点到相交点的距离是 b，相交点到链表终点的距离为 c 。我们使用两个指针，分别指向两个链表的头节点，并以相同的速度前进，若到达链表结尾，则移动到另一条链表的头节点继续前进 。按照这种前进方法，两个指针会在a + b + c 次前进后同时到达相交节点
————————————————
版权声明：本文为CSDN博主「legendarykk」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明 。


推荐阅读


上一篇：一文精通递归算法

下一篇：Kubernetes集群