【数据结构实战】打造属于你的超级链表

f狐o狸x

发布于 2024-11-19 17:32:38

1400

文章被收录于专栏：【数据结构实战篇】【数据结构实战篇】

前面几期我们对链表都进行了很详细的讲解，这期我们来给链表最后上点强度，打造出链表的ProMax版：带头双向循环链表

一、打造带头双向循环链表

1.1 带头双向循环链表概念及结构

前面几期中介绍过，链表的种类一共有三种，单向和双向的，带头和不带头的，循环和不循环的，这三种组合起来一共就有2 * 2 * 2 = 8种链表

这里我们实现最难的也是最常用的链表：带头双向循环链表

1.2 带头双向循环链表实现

其实他只是看着结构复杂，用起来很方便的，和纸老虎一样

1.2.1 链表初始化

于单链表不同，带头双向循环链需要先初始化一下

typedef int ListDataAType;

typedef struct ListNode
{
	ListDataAType Data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* InitList()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	if (head == NULL)
	{
		perror("InitList::malloc");
		return NULL;
	}
	head->next = head;
	head->prev = head;
	return head;
}

1.2.2 尾插尾删

有了这个结构以后，哨兵为的前一个就是尾节点，因此找尾很方便，操作也很简单

//尾插
void PushBack(ListNode* phead, int x)
{
	assert(phead);
	//找尾
	ListNode* tail = phead->prev;
	//尾插
	ListNode* NewNode = BuyListNode(x);
	tail->next = NewNode;
	NewNode->prev = tail;
	NewNode->next = phead;
	phead->prev = NewNode;
}

//尾删
void PopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	//找尾
	ListNode* tail = phead->prev;
	//尾删
	ListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}

1.2.3 头插头删

//头插
void PushFront(ListNode* phead, int x)
{
	assert(phead);
	ListNode* NewNode = BuyListNode(x);
	NewNode->next = phead->next;
	phead->next->prev = NewNode;
	NewNode->prev = phead;
	phead->next = NewNode;
}

//头删
void PopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

1.2.4 任意位置插入删除

//任意位置插入
void ListInsert(ListNode* pos, int x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* NewNode = BuyListNode(x);
	NewNode->next = pos;
	pos->prev = NewNode;
	NewNode->prev = prev;
	prev->next = NewNode;
}

//任意位置删除
void ListEarse(ListNode* pos)
{
	assert(pos);
	assert(pos->next != pos);
	ListNode* prev = pos->prev;
	prev->next = pos->next;
	pos->next->prev = prev;
}

这样我们就可以把前面的头插、头删、尾插、尾删改为：

//尾插
void PushBack(ListNode* phead, int x)
{
	assert(phead);
	ListInsert(phead, x);
}

//尾删
void PopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListEarse(phead->prev);
}

//头插
void PushFront(ListNode* phead, int x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

//头删
void PopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListEarse(phead->next);
}

1.2.5 销毁链表

养成好习惯，有借有还，再借不难

//销毁链表
ListNode* DestoryList(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

以上就是带头双向循环链表的全部实现，接下来我们再来几个和链表有关的题来练习一下

二、相交链表

力扣链接：相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

2.1 题目分析

这个题可以先让A链表和B链表全部走完一遍，分别记录他们的长度len1和len2，再让长的链表的头结点先走| len1 - len2 |步，在和len1 一起走，这样当他俩相等的时候，就是第一个交点

2.2 解题代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int len1 = 0;
    int len2 = 0;
    struct ListNode * cur1 = headA;
    struct ListNode * cur2 = headB;
    while(cur1)
    {
        cur1 = cur1->next;
        len1++;
    }
    while(cur2)
    {
        cur2 = cur2->next;
        len2++;
    }
    cur1 = headA;
    cur2 = headB;
    int k = len1 - len2;
    while(k)
    {
        if(k > 0)
        {
            cur1 = cur1->next;
            k--;
        }
        else
        {
            cur2 = cur2->next;
            k++;
        }
    }
    while(cur1 && cur2)
    {
        if(cur1 == cur2)
        {
            return cur1;
        }
        else
        {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
    }
    return NULL;
}

三、判断链表中是否有环

力扣链接：环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中存在环 ，则返回 true 。否则，返回 false 。

3.1 题目分析

用快慢指针，快指针一次走两步，慢指针一次走一步，这样如果链表有环的话，快指针一定可以遇到慢指针，如果没有环，那么快指针一定会变成空（走到链表尾部了）

3.2 解题代码

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

3.3 证明思路

这题难的是如何证明快指针一定能遇到慢指针，如下图，假设慢指针到节点的时候，快指针距离慢指针还有x步

快指针一次走两步，慢指针一次走一步，因此他两每走一次，他们的距离都回缩小x，这样当他面走了x次以后，他们的距离将会变为0，也就是快指针遇到了慢指针

跟紧步伐，我们再来一个更难的题

四、返回链表开始入环的第一个结点

力扣链接：环形链表||

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

4.1 题目分析

假设慢指针走了 l + x步到后快指针遇到慢指针，环有c个节点，快指针就走了 l + n * c + c - x（因为不知道慢指针进来前，快指针已经转了多少圈，所以用n来表示）

于是就有了这样的表达式：

通过上图分析，我们发现：l = n * c - x ，他意味着一个指针从相遇点出发，一个指针从头节点出发，当他两相等时，刚好就是进入环的第一个节点！！！

4.2 解题代码

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * cur1 = head;
    struct ListNode * cur2 = NULL;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            cur2 = fast;
            break;
        }
    }

    while(cur1 && cur2)
    {
        if(cur1 == cur2)
        {
            return cur1;
        }        
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return NULL;
}