c++链表详解（概念+例题）

学不懂链表，写个博客浅浅记录一下链表的学习叭。

一、数组与链表的区别

面试中除了会问到栈和队列的区别，还可能会询问数组（顺序表）与链表的区别。我们也可以先从熟悉的数据结构：数组，通过分析它和链表的区别来体会链表的特征。

二、单链表的介绍

1、单链表的结构

（1）图示

（2）代码

struct Listnode
{
    int data;
    Listnode* next;
};

2、头插

void Listcreatf(Listnode** head,int x)
{
    Listnode* newnode=new Listnode {x,NULL};
    newnode->next=*head;  //新指针指向原来的头指针
    *head=newnode;  //新指针成为头指针
}

注意：函数的第一个参数类型应该为二级指针，因为涉及到改变/初始化头节点，这个操作需要为一级指针的值赋值。

3、单链表的创建（尾插）

void Listcreatb(Listnode** head,int x)
{
    //用new来创建一个新指针，值为x，指向为空   
    Listnode* newnode=new Listnode {x,NULL};
    if(*head==NULL){  //如果是空链表，将newnode作为头节点
        *head=newnode;
    }
    else{
        Listnode* tail=*head;  //每次插入新的节点都需要从头遍历
        while(tail->next!=NULL)  //目的是找到尾节点（它的指向为空）
            tail=tail->next;
        tail->next=newnode;  //将新节点连接在尾节点后面，作为新的尾节点
    }
}

4、链表的释放

void Listfree(Listnode** head)
{
	Listnode* cur;  //新建一个节点
    while(*head){
        cur=*head;  //cur指向当前的头节点
        *head=cur->next;  //下一位节点成为头节点
        delete(cur);   //删除头节点
        cur=nullptr;  //必须置空，否则会成为野指针
    }
}

5、链表的打印

void Listprint(Listnode* head)
{
   listnode* cur=head;  //cur节点指向头节点
   while(cur){
      cout<<cur->data<<"->";  //依次打印
      cur=cur->next;
   }
}

6、删除链表中的节点

（1）删除头节点

void Listdeletef(Listnode** head)
{
   if(*head==NULL)
      return;
   else{
      Listnode* newnode=(*head)->next;
      delete(*head);
      *head=newnode;
   }
}

（2）删除尾节点

void Listdeleteb(Listnode** head)
{
   if(*head==NULL) //空链表
      return;
   if((*head)->next==NULL){  //只有一个节点
      delete(*head);
      *head=n;  //需要置空
   }
   else{
      Listnode* cur=*head;  
      Listnode* tmp=NULL;  
      while(cur->next){
         tmp=cur;
         cur=cur->next;  //找到尾节点
      }
      delete(cur);
      cur=NULL;
      tmp->next=NULL;  //tmp成为尾节点
   }
}

（3）删除等于给定值的所有节点

注意这个函数里会返回头节点因为函数参数只需要是一级指针。

Listnode* Listdelete(Listdode* head,int x)  
{
   Listnode* tmp=NULL;Listnode* cur=head;
   while(cur){
      if(cur->data==x){
         if(cur==head){   //如果头节点就是要删除的节点
            head=cur->next;
            delete(cur);
            cur=head;
         }
         else{
            tmp->next=cur->next;
            delete(cur);
            cur=tmp->next;
         }
      }
      else{
         tmp=cur;
         cur=cur->next;
      }
   }
   return head;
}

（4）删除指定位置的节点

void  Listdeletepos(Listnode** head,Listnode* pos)
{
   if(*head==pos){
      *head=pos->next;
      delete(pos);
      pos=nullptr;
   }
   else{
      Listnode* cur=*head;
      while(cur->next!=pos){
         cur=cur->next;
      }
      cur->next=pos->next;
      delete(pos);
      pos=nullptr;
   }
}

7.链表元素的查找

Listnode* Listfind(Listnode* head,int x)
{
	Listnode* cur=head;
   while(cur){
      if(cur->data==x)
         return cur;
      else
         cur=cur->next;
   }
   return NULL;
}

8.在指定位置后插入节点

void Listinsertb(Listnode* pos,int x)
{
   Listnode* newnode=new Listnode {x,NULL};
   newnode->next=pos->next;
   pos->next=newnode;
}

三、单链表的应用&例题

1.链表反转

力扣题目连接：206. 反转链表 - 力扣（LeetCode）

方法一：迭代

class Solution{
	public:
   	ListNode* reverseList(ListNode* head){
         ListNode* prev=nullptr;
         ListNode* curr=head;
         while(curr){
            ListNode* next=curr->next;
            curr->next=prev;
            pre=curr;
            curr=next;
         }
      }
}

**->**图解分析：

方法二：递归

class Solution{
	public:
   	ListNode* reverseList(ListNode* head){
         if(!head||!head->next)
            return head;
         ListNode* newhead=reverseList(head->next);
         head->next->next=head;
         head->next=nullptr;
         return newhead;
      }
}

2.找到链表的中间节点

力扣题目链接：876. 链表的中间结点 - 力扣（LeetCode）

题目描述：给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

方法一：遍历法

先遍历一遍找到一共有多少个节点，再遍历一遍找到中间节点。当链表长度较长的时候，这种方法较为浪费时间。下面的方法只需要遍历一次。

方法二：快慢指针法：

定义两个指针，慢指针依次只走一步，快指针一次走两步。当快指针走到终点时，慢指针就刚好走到了中间节点。

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

3.移除重复节点

力扣题目链接：面试题 02.01. 移除重复节点 - 力扣（LeetCode）

题目描述：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

哈希表法：

ListNode* removeDuplicateNodes(ListNode* head) {
   ListNode* pre=NULL,*cur=head;  //前后指针
   unordered_set<int> list;  //初始化哈希表
   while(cur){  //当指针不为空
      if(list.find(cur>val)==list.end()){  //没有该元素
         list.insert(cur->val);  //插入
         pre=cur;
      }     
      else
         pre->next=cur->next;  //如果表中已经有该元素，删除该指针
      cur=cur->next;
   }
   return head;  //若头指针就为空则直接返回
}

4.找到链表的倒数第k个指针

力扣题目链接：

int kthToLast(ListNode* head, int k) {
	ListNode* pre,*cur;
   pre=cur=head;
   while(k--)
      pre=pre->next;
   while(pre){
      pre=pre->next;
      cur=cur->next;
   }
   return cur.val;
}

5.判断链表是否为回文链表

力扣题目链接：

方法一：复制元素到数组中再进行判断

bool isPalindrome(ListNode* head) {
	vector<int> list;
   while(head!=nullptr){
      list.emplace_back(head->val);
      head=head->next;
   }
   for(int i=0,j=list.size()-1;i<j;i++,j--){
      if(list[i]!=list[j])
         return false;
   }
   return true;
}

方法二：递归

class Solution {
    ListNode* frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

6.相交链表

力扣题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

双指针法：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	if(headA==nullptr||headB==nullptr)
      return null;
   ListNode* n1=headA,*n2=headB;
   while(n1!=n2){
      n1=n1==nullptr?headB:n1->next;
      n2=n2==nullptr?headA:n2->next;
   }
   return n1;
}

7.环路检测

力扣题目链接：面试题 02.08. 环路检测 - 力扣（LeetCode）

题目描述：给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

哈希表法：

ListNode *detectCycle(ListNode *head) {
   unordered_set<ListNode*> list;
   while(head!=nullptr){
      if(list.count(head))
         return head;
      list.insert(head);
      head=head->next;
   }
   return null;
}