《数据结构教程》2.4 - 2.5 循环链表与双向链表

245 阅读1分钟

前面讨论了线性表的顺序存储方式(顺序表)和链式存储方式(线性链表),这两节讨论线性表的另一种形式的链式存储结构:循环链表。

循环链表

循环链表指的是链表的最后一个链结点的指针域指向链表的第一个结点。有时候为了方便,我们在链表的第一个结点前设置一个特殊结点,称之为 头结点。于是循环链表的最后一个结点的指针域指向的是头结点。

双向链表

顾名思义,双向链表指在链表的每一个结点中除了数据域之外,设置两个指针域,一个指向直接前驱结点,一个指向直接后继结点。

双向链表可以是循环的,也可以不是循环的,根据需要也可以选择设置头结点。

经典算法题

判断链表是否带环

leetcode 141. 环形链表

设置两个指针进行赛跑是解决关于循环链表的经典算法。简单来说,首先在头结点处设置快慢指针,两者同时向后移动,快指针一次移动两步,慢指针一次移动一步,如果链表是带环的,那么快指针一定会追上慢指针。

bool hasCycle(struct ListNode *head) {
    struct ListNode *right = head;
    struct ListNode *left = head;
    
    while (right != NULL && right -> next != NULL && right -> next -> next != NULL) {
        right = right -> next -> next;
        left = left -> next;
        
        if (left == right) {
            return 1;
        }
    }
    
    return 0;
}