[数据结构与算法] 真的细-----＞链表OJ（下）和双向带头循环链表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 真的细-----＞链表OJ（下）和双向带头循环链表 -> 正文阅读

[数据结构与算法]真的细-----＞链表OJ（下）和双向带头循环链表

本篇文章的主要内容

1.合并两个有序链表
2.基于x的值分割两个链表
3.输入两个链表，返回两个链表的相交节点
4.给定一个链表，判断链表是否有环
5.给定一个链表，返回链表开始进入环的节点，如果没有环，返回NULL
6.复制带随机指针的链表
7.双向带头循环链表的增删查改

在上一篇博客里，我们已经接触过一些链表的OJ题了，这些题目相对于今天的题目只是一个热身，也就是今天的题目的难度会上一个大台阶！今天的题目就能考验出你对链表增删查改的理解和控制能力！好了，话不多说，开始进入今天的主题。

力扣

题目的详细信息如下

?在顺序表的那一篇博客里，我们做了一道合并两个有序数组的题目，那道题我们使用了尾插的方式进行处理，这给了我们一个方向，那么我们可不可以也考虑用尾插的方式来分析一下：

定义两个指针head和tail，当list1和list2指针非空的时候取下值较小的节点连接到tail的后面，

接着重复这一过程，当list1和list2两者中其中一个为空的时候，就把非空的链表连接到新的链表后面去，最后返回新的头节点就可以了。

具体的图解如下：

?那么我们就可以上手写出代码：


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     struct ListNode* head=NULL,*tail=NULL;
     if(NULL==list1)
     {
         return list2;
     }
     if(NULL==list2)
     {
         return list1;
     }
     while(list1 && list2)
     {
         if(list1->val <list2->val)
         {
             if(NULL==tail)
             {
                head=tail=list1;
             }
             else
             {
                 tail->next=list1;
                 tail=list1;
             }
             list1=list1->next;
         }
         //处理list1->val >list2->val
         else
         {
                if(NULL==tail)
             {
                head=tail=list2;
                
             }
             else
             {
                 tail->next=list2;
                 tail=list2;
             }
             list2=list2->next;
         }
     }
     //处理两者链表其中一个为空出循环的情况
     if(list1)
     {
         tail->next=list1;
     }
     if(list2)
     {
         tail->next=list2;
     }
     return head;
}

其实这份代码还是可以在进一步简化，在手撕单链表那里我们提过链表是可以带一个哨兵位的头节点的，这个哨兵位只是起到一个站岗的作用，并不存储有效的数据！我们这里的题解是使用不带哨兵位的头节点的做法，那么就是要处理开始的时候链表是空的情况，那么我们如果使用带头节点的单链表就可以不用考虑开始这个问题，因为头节点永远都在！

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //哨兵位头节点，不存储有效数据
    struct ListNode* phead=(struct ListNode*)malloc(sizeof(struct ListNode));
    assert(phead);
    phead->val=101;
    phead->next=NULL;
    struct ListNode* tail=phead;
    //尾插的逻辑
    while(list1 && list2)
    {
       if(list1->val <list2->val)
       {
           tail->next=list1;
           list1=list1->next;
           
       }
       else
       {
           tail->next=list2;
           list2=list2->next;
       }
       tail=tail->next;
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    //最后释放哨兵位头节点，防止内存泄露
    struct ListNode* head=phead->next;
    free(phead);
    return head;
}

这道题的难点并不在于解决问题的思想，而是在于你对代码的控制能力，而接下来的这道分割链表则就是能真真正正地考察出你对链表的理解和代码控制能力！

链表分割_牛客题霸_牛客网

?牛客网把这道题标成较难。确实一个原因是因为这道题目对代码能力要求高，另外一个方面就是牛客网本身做的不是很完善，这道题没有提供测试用例也提高了难度，所以我们自己来提供一个测试用例来分析：

测试用例：{1，3，2，4，4，5，6，7}? x==4

和合并两个有序链表一样，这道题我们也是采用取节点尾插的方式，只不过相对来说这里需要处理两个链表，小于x的和大于x的，最后我们把两个链表合并得到结果

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lessHead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* greatHead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* lessTail=lessHead,*greatTail=greatHead;
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val <x)
            {
                lessTail->next=cur;
                lessTail=cur;
                cur=cur->next;
            }
            else
            {
                 greatTail->next=cur;
                 greatTail=cur;
                cur=cur->next;
            }
        }
        lessTail->next=greatHead->next;
        struct ListNode* head=lessHead->next;
        free(lessHead);
        free(greatHead);
        lessHead=NULL;
        greatHead=NULL;
        return head;
    }
};

提交代码，系统提示我们内存超限：

?为什么会内存超限呢？因为我们的代码在一些特定的情况下是死循环！

?所以在连接完这个链表以后，greatTail的next一定要置空！

AC代码如下：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lessHead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* greatHead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* lessTail=lessHead,*greatTail=greatHead;
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val <x)
            {
                lessTail->next=cur;
                lessTail=cur;
                cur=cur->next;
            }
            else
            {
                 greatTail->next=cur;
                 greatTail=cur;
                cur=cur->next;
            }
        }
        lessTail->next=greatHead->next;
        greatTail->next=NULL;
        struct ListNode* head=lessHead->next;
        free(lessHead);
        free(greatHead);
        lessHead=NULL;
        greatHead=NULL;
        return head;
    }
};

相对于带头节点的方式来说，没有带哨兵位的头节点的链表处理方式就会比较复杂一点，在这里我提供一下对应的解题代码，有兴趣的读者可以自行进行研究，这里我就不在多做介绍：

class Partition {
public:
    //不带哨兵位头节点的解法
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* cur=pHead;
        ListNode* lessHead=NULL;
        ListNode* lessTail=NULL;
        ListNode* greatHead=NULL;
        ListNode* greatTail=NULL;
        while(cur)
        {
            if(cur->val <x)
            {
                if(lessHead==NULL)
                {
                    lessHead=lessTail=cur;
                }
                else
                {
                    lessTail->next=cur;
                    lessTail=lessTail->next;
                }
            }
            else
            {
                if(greatHead==NULL)
                {
                    greatHead=greatTail=cur;
                }
                else
                {
                    greatTail->next=cur;
                    greatTail=greatTail->next;
                }
            }
            cur=cur->next;
        }
        //连接的情况
        if(lessTail &&  greatTail)
        {
            lessTail->next=greatHead;
            greatTail->next=NULL;
        }
        //lesshead为空
       else if(lessTail==NULL)
       {
           return greatHead;
       }
       return lessHead;
        
    }
};

怎么样？这道较难果然还是名不虚传吧！这道题的难点就是特定的情况下链表会形成环！第4和第5就是和链表成环有关系的，我们接下来讲的第三题是求链表的公共结点，设计到两个链表相交的问题

首先，我们要明白链表相交和链表成环这两个概念：链表相交是相对于两个链表而言，而链表成环是相对于一个链表来说，也就是对象数目不同！

接下来我们来看这么一道和链表相交有关的题目：

力扣

输入两个链表，返回两个链表的相交节点

?这道题的解题思路如下：

?解题代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA=headA,*tailB=headB;
    int lenA=1,lenB=1;
    while(tailA->next)
    {
        ++lenA;
        tailA=tailA->next;
    }
    while(tailB->next)
    {
        ++lenB;
        tailB=tailB->next;
    }
    //尾部不同，没有交点，直接返回
    if(tailA !=tailB)
    {
        return NULL;
    }
    //算法：两个链表从同一个位置开始走，如果相同，最直接返回
    int gap=abs(lenA-lenB);
    struct ListNode* shortList=headA,*longList=headB;
    if(lenA>lenB)
    {
        shortList=headB;
        longList=headA;
    }
    //长的先走
    while(gap--)
    {
        longList=longList->next;
    }
    //同时走
    while(longList && shortList)
    {
        if(longList==shortList)
        {
            return shortList;
        }
        longList=longList->next;
        shortList=shortList->next;
    }
    //不会走到这里，只是为了编译通过
    return NULL;
}

这里我们做了一个很巧妙的处理，我们使用longlist和shortlist来替代完成寻找公共交点的工作，我们默认A是长链表，B是短链表，如果不是我们就更正一下，这样就替代了冗长的A和B长短判断的逻辑！

?接下来，进入链表里面比较有意思的一类问题：链表成环问题，可以这么说：链表成环问题在实际的面试中算是考察链表问题里面比较复杂的了！

力扣? ? ?给定一个链表，判断链表是否有环

力扣? ? ??给定一个链表，返回链表开始进入环的节点，如果没有环，返回NULL

?我们先来看第一题：

?那么在链表带环问题里面，快慢指针是很好的解法，慢指针一次走一步，快指针一次走两步，如果链表带环，那么快指针一定会在环里面追上慢指针（稍后证明），否则最后fast就会走到空，基于这个性质我们就可以上手写代码了！

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast && fast->next)
    {  
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    //循环结束，肯定就是没有环
    return false;
}

如果这道题考察你写代码的话那就是没什么难度，也没有什么考察的实际价值！?那么为什么快指针走两步，慢指针走一步一定能相遇呢？如果快指针一次走3步，慢指针走1步呢？快指针一次走4步呢？这曾经是一家公司的面试的问题？接下来我们通过图解来证明为什么快指针一次走两步，慢指针一次走一步可以相遇。

?那么fast1次走3步，slow一次走一步，最终两个指针能够在环里相遇吗？

答案是不一定，在特殊的情况下，两个指针永远追不上！这时候能否追上还和环的长度C相关！

?那么当N是偶数的时候，二者刚好能够追上，那么当N是奇数的时候，最终fast和slow的距离变成了-1，这时候对应的slow和fast错开了！两者的相对位置如下图：

?那么针对于fast一次走4步，slow一次走1步，最终实际距离可能就变成了C-1或C-2，分析的方式与fast1次3步,slow一次1步的情况类似，这里就不在赘述，感兴趣的读者可以自行研究。

怎么样？是不是深究起来还是很有意思的？那么接下来这道题目则就是基于我们上面这样的分析过程得出来的一个数学推导公式，有了这样一个公式，我们就能很快解决下面这个问题：

力扣

给定一个链表，返回链表开始进入环的节点，如果没有环，返回NULL

?这道题运用了一个性质就可以解决：一个指针从头节点开始走，另一个指针从相遇的节点开始走，如果链表带环，那么最终这两个环将会在环的入口处相遇！！！

接下来我们就对这个性质定义进行推导证明：

?了解了这个性质以后，解决这道题就很简单了。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast && fast->next)
    {   

        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {  //一个从入口点开始，另一个从相遇点开始，必定能在入口处相遇
            struct ListNode* meet=slow;
            while(meet !=head)
            {
                head=head->next;
                meet=meet->next;
            }
            
            return meet;
        }
    }
    //走到这里就是没有环
    return NULL;
}

假如我不知道这么一个性质的话，那么我还有方法解决这个问题吗？还记得我们前面讲的相交链表吗？这里我们就可以把链表的环解开从而转换成求两个相交链表的问题，具体的步骤就是找到快慢指针相遇的节点，然后取下meet的下一个节点作为一个新链表的头，在把meet的next置空，求出公共节点即为链表环的入口！这里我就放一张图示，有兴趣的读者可以自行实现代码逻辑

?讲完了链表成环问题，接下来再来上一道链表的硬菜，这道题可以说是目前我们接触的链表的OJ题中逻辑最复杂的题目了，接下来请跟紧我的脚步，这道题确实不太好理解

力扣

复制带随机指针的链表

这道题目讲的是复制一个链表，这个链表和原来的链表相同并且独立，题目的描述文字很多多很复杂，我们从测试用例来分析题目的意思：

?接下来，我们需要复制这个链表，那么我们处理的方式分三步走

1.忽略random指针，拷贝和原来单链表一样的random指针，并将新节点尾插到原来的链表里

2.拷贝random指针

3.将新的链表从原来的链表中解下来

看图说话：

?最后一步的取节点尾插就和前面的类似，这里就不在多讲了，下面我们来实现一下代码：

struct Node* copyRandomList(struct Node* head) {
 struct Node* cur=head;
 //1，拷贝节点连接在原节点的后面
  while(cur)
  {
      struct  Node*copy=(struct Node*)malloc(sizeof(struct  Node));
      copy->val=cur->val;
      copy->next=cur->next;
      cur->next = copy;
      cur=copy->next;
  }
  //2.链接拷贝节点的random(拷贝节点的random在原节点random的后面)
  cur=head;
  while(cur)
  {
      struct  Node*copy=cur->next;
      if(cur->random== NULL)
      {
          copy->random= NULL;   
      }
      else
      {
        copy->random=cur->random->next;
      }
      cur=copy->next;
  }
  //3.拷贝节点解下来，连接在一起
    cur=head;
   struct Node* copyHead=NULL;
    struct Node *copyTail=NULL;
  while(cur)
  {
    struct Node*copy=cur->next;
    struct Node*next=copy->next;
    if(copyTail==NULL)
    {
        copyHead=copyTail=copy;
    }
    else
    {
      copyTail->next=copy;
      copyTail=copyTail->next;
    }
    cur=next;
  }
  return copyHead;
}

?最后，我们来讲一讲链表结构里最优秀的链表结构---->双向带头循环链表，这个链表真的是做到了在任何位置插入和删除时间复杂度都是O（1）的一个结构，这也是C++标准库实现的list的结构，接下来我们就来实现这样一个链表

如图，双向带头循环链表的结构如下：

?从这张图片不难看出，每个节点都有两个指针域，前驱（prev）和后继（next）,另外这个链表还做了一个巧妙地设计：就是让尾节点的next指向head,head的prev指向尾节点，这样就形成了一个环，或许你觉得这个链表的结构很复杂，但是请静下心来跟着我一起来研究，你就会发现这种结构优势带来的魅力！！！

头文件：list.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
//申请节点
ListNode* BuyListNode(LTDataType x);
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

首先我们是有头节点链表，意味着即使没有数据，链表也不是空！所以在最开始得时候，我们要创造哨兵位得头节点，并且让这个节点的prev和tail都指向自己（保持循环结构）！

//申请节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{   //这个数据没有实际意义，可以随便赋值，因为这个节点是哨兵位
	ListNode* phead = BuyListNode(INT_MAX);
	//环头和环尾指向自己
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

接下来就是处理尾插的情况，这时候结构的优势就体现出来了！如果是单向链表，那么你需要遍历找尾节点，然而在双向循环就不用，因为头节点的前驱就是尾节点！

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;
}

而头插的逻辑就更加的简单，phead的next就是头节点，不过在插入之前注意先保存原来的头节点

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* Next = pHead->next;
	newnode->prev = pHead;
	pHead->next = newnode;
	newnode->next = Next;
	Next->prev = newnode;
}

接下来实现insert方法，由于链表的结构优势，我们直接可以找到pos的前驱和后继，从而实现直接的连接！

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	newnode->prev = posPrev;
	newnode->next = pos;
	posPrev->next = newnode;
	pos->prev = newnode;
}

讲完了插入，接下来我们来讲删除，那么同样从尾删开始

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	//哨兵位不能删除
	assert(pHead->next!=pHead);
	ListNode* tail = pHead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tail = NULL;
	tailPrev->next = pHead;
	pHead->prev = tailPrev;
}

同理头删也是一样：

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
   //哨兵位节点不能删除
	assert(pHead->next != pHead);
	ListNode* Next = pHead->next->next;
	free(pHead->next);
	pHead->next = Next;
}

接下来，我们实现在任意位置删除的算法Erase,和insert的处理方式很相似，我们需要同时保存pos的prev和next，接着将pos释放：

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	free(pos);
	pos = NULL;
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

这些主要的实现了，剩下的代码就没有什么难度了，完成的实现代码如下：

#define  _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//申请节点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* phead = BuyListNode(INT_MAX);
	//环头和环尾指向自己
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	ListNode* cur = pHead;
	assert(pHead);
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{   
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	//哨兵位不能删除
	assert(pHead->next!=pHead);
	ListNode* tail = pHead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tail = NULL;
	tailPrev->next = pHead;
	pHead->prev = tailPrev;
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = BuyListNode(x);
	ListNode* Next = pHead->next;
	newnode->prev = pHead;
	pHead->next = newnode;
	newnode->next = Next;
	Next->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);
	ListNode* Next = pHead->next->next;
	free(pHead->next);
	pHead->next = Next;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur !=pHead)
	{
		if (x == cur->val)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	newnode->prev = posPrev;
	newnode->next = pos;
	posPrev->next = newnode;
	pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	free(pos);
	pos = NULL;
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

结语：

本篇博客讲述了较为复杂的链表OJ题，其中链表成环问题和复制带随机指针的链表问题值得读者好好去深思一下，最后希望大家能够学有所成，如果有不足之处还望指点一二！！！