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

-> 数据结构与算法 -> 链表操作，万变不离其宗 -> 正文阅读

[数据结构与算法]链表操作，万变不离其宗

1. 链表基本介绍

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。实际中链表的结构非常多样，实际中最常用还是两种结构：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。结构虽然复杂，但在操作上有很多优势。

2. 无头单向不循环链表

这是常用的一种链表，oj题中经常使用，面试时也常用
实现链表的完整程序

3. 带头双向循环链表

在这里插入图片描述
带头双向循环链表的优势体现在对它的基本操作中：
实现一个有增删改等功能的带头双向循环链表

4. 链表经典题目分析

①移除链表元素

题目链接

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
题目答案及分析

②反转链表

题目链接

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

在这里插入图片描述
方法一：
定义三个指针n1 n2 n3，n1记录上一个节点位置，n2为当前位置，n3是下一个节点位置，修改时当前位置指向上一个位置，然后n1,n2,n3都后移。如图：

程序如下：

struct ListNode* reverseList(struct ListNode* head){
        if (!head)
		return head;
	struct ListNode* n1 =NULL;//记录上个节点位置
	struct ListNode* n2 = head;//当前位置
	struct ListNode* n3 = head->next;//记录下个位置
	while (n2)
	{
		n2->next=n1;
        n1=n2;
        n2=n3;
		if(n3)
        n3=n3->next;
	}
    return n1;
}

方法二：
遍历节点依次头插，使初始尾节点变成新头结点

struct ListNode* reverseList(struct ListNode* head){
      struct ListNode* newhead=NULL;
      struct ListNode* cur=head;
      while(cur)
      {
          struct ListNode* next=cur->next;
          cur->next=newhead;
          newhead=cur;
          cur=next;
      }
      return newhead;
}

③链表的中间结点

题目链接

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

思路：快慢指针法，慢指针走一步，快指针走两步。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast=head;
    struct ListNode* low=head;
    while(fast&&fast->next)
    {
        low=low->next;
        fast=fast->next->next;
    }
     return low;
}

④链表中倒数第k个节点

题目链接
在这里插入图片描述
思路：
快慢指针法更为方便，快指针先走k步，然后快慢指针同时走，注意考虑特殊情况。

程序如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
     if(!pListHead)
        return NULL;
     struct ListNode* low=pListHead;
     struct ListNode* fast=pListHead;
     while(k--)
     {
        if(fast==NULL)
            return NULL;
        fast=fast->next;
     }
     while(fast)
     {
        low=low->next;
        fast=fast->next;
     }
     return low;
}

⑤整合两个有序链表

题目链接

思路：创建新头，比较两个链表当前节点数值，小的在新链表后尾插，剩余的全部接上即可

程序如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
          if(!l1)
             return l2;
          if(!l2)
             return l1;
          struct ListNode* newhead=NULL;
          struct ListNode* tail=NULL;
          struct ListNode* cur1=l1;
          struct ListNode* cur2=l2;
          if(cur1->val<cur2->val)
          {
              newhead=l1;
              tail=l1;
              cur1=cur1->next;
          }
          else
          {
              newhead=l2;
              tail=l2;
              cur2=cur2->next;
          }
        
          while(cur1&&cur2)
          {
              if(cur1->val<cur2->val)
              {
                tail->next=cur1;
                tail=cur1;
                cur1=cur1->next;
              }
              else
              {
                tail->next=cur2;
                tail=cur2;
                cur2=cur2->next;
              }
          }
          if(cur1==NULL)
            tail->next=cur2;
          else
            tail->next=cur1;

         return newhead;
}

小技巧：
创建新头那段代码有点长，可以开辟一个哨兵节点，然后直接开始比较，最后返回要求的指针，释放哨兵节点
在这里插入图片描述

⑥排序链表部分节点

题目链接

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针

思路：开辟两个新头，小于x的链接在一起，其余链接在一起，然后两条链链接在一起

程序如下：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
         struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
         lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
         greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next=cur;
                lessTail=cur;
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=cur;
            }
            cur=cur->next;
        }
        
        greaterTail->next=NULL;
        
        lessTail->next=greaterHead->next;
        struct ListNode* p=lessHead->next;
        free(lessHead);
        free(greaterHead);
        return p;
    }
};

⑦链表的回文结构

题目链接

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：找到链表中间节点，将后半条链逆序，遍历比较。（可参考②，③）

class PalindromeList {
public:
//找到中间节点
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head;
    struct ListNode* low=head;
    while(fast&&fast->next)
    {
        low=low->next;
        fast=fast->next->next;
    }
     return low;
}
//链表逆序
struct ListNode* reverseList(struct ListNode* head)
{
      struct ListNode* newhead=NULL;
      struct ListNode* cur=head;
      while(cur)
      {
          struct ListNode* next=cur->next;
          cur->next=newhead;
          newhead=cur;
          cur=next;
      }
      return newhead;
}
 
bool chkPalindrome(ListNode* A) 
{
       struct ListNode * mid = middleNode(A);
       struct ListNode * rhead = reverseList(mid);//逆序后的新头为rhead
       
       struct ListNode *head = A;
       while(head&&rhead)
       {
           if(head->val!=rhead->val)
               return false;
           
           head=head->next;
           rhead=rhead->next;
       }
       return true;
}
};

⑧链表的公共节点

题目链接

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

思路：先判断链表是否相交，相交的链表最后一个节点应该是一样的。
如果相交，计算两链表的长度，定义两个指针指向两链表，长链表先走两链表长度差值步，然后两指针同时走，当走到公共节点前一个位置，next的值相同，找到。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   //确定两链表长度
    struct ListNode * curA = headA;
    struct ListNode * curB = headB;
    int lenA = 0, lenB = 0;
    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }
   //假设A更长，如果不是，交换即可
    struct ListNode * longList =headA;
    struct ListNode * shortList =headB;
    if(lenA<lenB)
    {
        longList=headB;
        shortList=headA;
    }
    //长链先走差值步
    int gap = abs(lenA-lenB);
    while(gap--)
    {
        longList = longList->next;
    }
   //同时走，判断有无相交
    while(longList&&shortList)
    {
        if(longList == shortList)
        {
            return longList;
        }
        shortList = shortList->next;
        longList = longList->next;
    }

    return NULL;
}

⑨带环链表

a.判断链表是否有环

题目链接

给定一个链表，判断链表中是否有环

思路：快慢指针同时从头走，慢指针走一步，快指针走两步，如果有环，快慢指针会相遇

程序如下：

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

b.返回带环链表的入环位置

题目链接

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

思路：
有这样一个结论：用a中方法判断链表是否有环，如果有，可以找到快慢指针相遇处，使一个指针从相遇处一步一步走，使另一个指针同时从头一步一步走，他们最终会在入环处相遇
证明过程：
（该过程值得读者思考的细节很多）
在这里插入图片描述

程序如下：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* low=head;
    struct ListNode* fast=head;
    while(fast&&fast->next)
    {
        low=low->next;
        fast=fast->next->next;
        if(low==fast)
        {
            struct ListNode* meet=low;
            while(meet!=head)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

⑩每个节点包含随机指针的链表

题目链接

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点

在这里插入图片描述
思路：
首先想到，遍历复制，但是当前位置的随机指针指向的节点可能还没有创建出来
方法之一：
在每个节点后插入一个新节点，然后给新节点的随机指针赋值，最后把刚才插入的所有新节点链接起来就复制成功了。
随机指针赋值的依据：每个新插入的节点复制的是现在它之前的老节点，老节点根据随机指针访问到另一个老节点，这个访问到的老节点后也插入了新节点，老节点——老节点和新节点——新节点的的相对距离一样，随机指针的指向就确定了。

程序如下：

struct Node* copyRandomList(struct Node* head) {
	if(head==NULL)
    return NULL;

    //拷贝节点在原来节点之后
    struct Node* cur=head;
    while(cur)
    {
        struct Node* next=cur->next;
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }

    //给随机节点赋值
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random)
        {
            copy->random=cur->random->next;
        }
        else
        {
            copy->random=NULL;
        }
        cur=copy->next;
    }

    //把新节点链接起来
    struct Node* copyhead,*copytail;
    copyhead=copytail=(struct Node*)malloc(sizeof(struct Node));
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;

        copytail->next=copy;
        copytail=copy;

        cur->next=next;
        cur=next;
    }

    struct Node* p=copyhead;
    copyhead=copyhead->next;
    free(p);
    return copyhead;
}