单链表经典算法题

gumidc

406人浏览 · 2026-04-24 20:46:52

gumidc · 2026-04-24 20:46:52 发布

1.移除链表元素

1.1思路一：

代码如下：

typedef struct ListNode ListNode;
while(head!=NULL&&head->val==val)
    {
        struct ListNode*temp=head;
        head=head->next;
        free(temp);
    }
    if(head==NULL)
    return NULL;
  ListNode* pcur=head;
  ListNode* prev=head;
  ListNode* pnext=head;
   while(pcur)
   {
    pnext=pcur->next;
   if(pcur->val==val)
   {
    prev->next=pnext;
   free(pcur);
   }
   else
   {
    prev=pcur;
   }
   pcur=pnext;
   }
   return head;
}

易错点：

1.头节点是val的情况未考虑到

2.pnext保存太晚

3.头处理后，注意链表删空的情况，返回NULL

4.注意prev只有在不删节点时才更新

1.2思路二：

找值不为val的节点，尾插到新链表中

代码如下：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* pcur=head;
    ListNode* NewHead,*NewTail;
    NewHead=NewTail=NULL;
    while(pcur)
    {
    if(pcur->val!=val)
    {
        //链表为空
        if(NewHead==NULL)
        {
            NewHead=NewTail=pcur;
        }
        else
        {
       NewTail->next=pcur;
       NewTail=NewTail->next;
        }
    }
    pcur=pcur->next;
    }
    if(NewTail)
    NewTail->next=NULL;
    return NewHead;
}

易错点：

1. 最后一次把5这个节点拿到新链表进行尾插的时候，这个节点的next也拿下来了，所以必须要将NewTail的next置空

2. 注意链表为空的情况

2.反转链表

2.1思路一：

把链表的每个节点，依次头插到新链表的前面

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    ListNode* NewHead=NULL;
    ListNode* pcur=head;
    while(pcur)
    {
        //提前保存当前节点的下一个节点
        ListNode* pnext=pcur->next;
        //头插
         pcur->next=NewHead;
         NewHead=pcur;
         //继续往后遍历
         pcur=pnext;
    }
    return NewHead;

2.2思路二：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    ListNode* n1,*n2,*n3;
    //判空
    if(head==NULL)
    return head;
    n1=NULL,n2=head,n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
return n1;
}

易错点：一定要判断链表是否为空

3.链表的中间节点

3.1思路一：

遍历，count记节点数，直接返回(count/2)节点的next节点

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    int count=0;
    ListNode* pcur=head;
    while(pcur)
    {
   pcur=pcur->next;
   count++;
    }
   int mid=count/2;
   pcur=head;
    for(int i=0;i<mid;i++)
    {
        pcur=pcur->next;
    }
    return pcur;
}

3.2思路二：

快慢指针

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

易错点：while里的fast与fast->next一定不能交换位置，因为如果fast为空，那么fast->next就是对空指针的解引用，代码一定会报错

4.合并两个有序链表

思路：创建新链表，遍历原链表，把较小的数拿到新链表进行尾插。

 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* l1=list1;
    ListNode* l2=list2;
ListNode* NewHead,*NewTail;
NewHead=NewTail=NULL;
if(l1==NULL)
{
    return l2;
}
if(l2==NULL)
{
    return l1;
}
while(l1&&l2)
{
    if(l1->val < l2->val)
    {
        if(NewHead==NULL)
        {
            NewHead=NewTail=l1;
        }
        else
        {
            NewTail->next=l1;
            NewTail=NewTail->next;
        }
        l1=l1->next;
    }
    else
    {
        if(NewHead==NULL)
        {
            NewHead=NewTail=l2;
        }
        else
        {
            NewTail->next=l2;
            NewTail=NewTail->next;
        }
        l2=l2->next;
    }
}
//跳出循环，说明l1或l2走到空了
 if(l1)
 {
NewTail->next=l1;
 }
 if(l2)
 {
NewTail->next=l2;
 }
 return NewHead;
 }

但是这个代码存在重复，我们如何优化一下呢？

这里我们可以让链表不为空，用malloc动态申请一块空间：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* l1=list1;
    ListNode* l2=list2;
    ListNode* NewHead,*NewTail;
    NewHead=NewTail=(ListNode*)malloc(sizeof(ListNode));
if(l1==NULL)
{
    return l2;
}
if(l2==NULL)
{
    return l1;
}
while(l1&&l2)
{
    if(l1->val < l2->val)
    {
        NewTail->next=l1;
        NewTail=NewTail->next;
        l1=l1->next;
    }
    else
    {
        NewTail->next=l2;
        NewTail=NewTail->next;
        l2=l2->next;
    }
}
//跳出循环，说明l1或l2走到空了
 if(l1)
 {
NewTail->next=l1;
 }
 if(l2)
 {
NewTail->next=l2;
 }
   ListNode* ret=NewHead->next;
   free(NewHead);
   NewHead=NULL;
   return ret;
 }

易错点：

1. 动态申请的空间必须要释放，释放前需要定义一个新变量保存NewHead->next的地址

2. 最后返回的值应该是NewHead的下一个节点，NewHead里面没有有效值，是系统随机分配的。

5.环形链表的约瑟夫问题

根据示例1，我们画下图进行分析：

根据题意，我们需要释放2节点，所以首先我们先创建两个变量prev与pcur，释放2之前先让prev->next指向pcur->next，然后再释放2，接着我们需要把编号1跟2挪动位置

循环此操作过程几次后得到如下图：

接下来一起写代码：

第一步：创建带环链表

这一步我们封装一个函数creatCircle。

首先要先创建第一个节点，这里我们再封装一个函数BuyNode，然后我们将数据尾插到链表中。最后首尾相连，链表成环

注意：该函数的返回值取决于我们接下来要怎么使用这个链表，由于返回尾节点ptail可以同时直接访问头节点，所以我们返回的是ptail

第二步：计数

我们用prev与pcur去接收ptail与ptail->next，然后我们用count来计数，count初始值为1，当count与m相等的时候，需要销毁pcur节点，否则prev与pcur各后移一位。

因为删到最后pcur->next会指向自己，如下图

所以可得循环while里的条件。

6.分割链表

6.1思路一：

在原链表上进行修改，若pcur节点的值小于x，往后走；

若pcur节点的值大于等于x，尾插在原链表后，删除旧节点。

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    ListNode phead;
    phead.next=head;
    ListNode* prev=&phead;
    ListNode* pcur=head;
    ListNode* ptail=head;

    while(ptail->next)
    {
        ptail=ptail->next;
    }
    ListNode* newPtail=ptail;
  while(pcur!=ptail)
  {
  if(pcur->val<x)
  {
    prev=pcur;
    pcur=pcur->next;
  }
 else
{
  ListNode* temp=pcur;
  pcur=pcur->next;
  prev->next=pcur;

  newPtail->next=temp;
  newPtail=newPtail->next;
  newPtail->next=NULL;
}
  }
  return phead.next;
}

6.2思路二：

创建新链表，遍历原链表，若pcur节点的值小于x，头插在新链表中；

若pcur节点的值大于或等于x，尾插在新链表中。

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    ListNode newHead;
    newHead.next=NULL;
    ListNode* newTail=&newHead;
    ListNode* pcur=head;
   while(pcur)
   {
    ListNode* nextNode=pcur->next;
  if(pcur->val<x)
  {
    if(newHead.next==NULL)
    {
        newTail=pcur;
    }
    pcur->next=newHead.next;
    newHead.next=pcur;
  }
  else
  {
    newTail->next=pcur;
    newTail=newTail->next;
  }
  pcur=nextNode;
   }
   newTail->next=NULL;
   return newHead.next;
}

易错点：

1. newTail需要在第一次进行的是头插的时候更新

2. 未提前保存nextNode

3. 尾部未置空

6.3思路三：

创建两个新链表，一个小链表，一个大链表

然后我们将小链表的尾节点与大链表的第一个节点首尾相连

易错点：

1. 原链表中5的next指针指向的是2，如果不做处理，就会造成死循环，如下图：

2. 一定要先将greatertail的next指针进行初始化，再将小链表尾节点与大链表的第一个节点相连

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
  ListNode* lessHead,*lessTail;
  ListNode* greaterHead,*greaterTail;
  lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));
  greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));

  ListNode* pcur=head;
  while(pcur)
  {
    if(pcur->val<x)
    {
        lessTail->next=pcur;
        lessTail=pcur;
    }
    else
    {
        greaterTail->next=pcur;
        greaterTail=pcur;
    }
    pcur=pcur->next;
  }

  greaterTail->next=NULL; //对next指针初始化+避免代码出现死循环

  lessTail->next=greaterHead->next;

  ListNode* ret=lessHead->next;
  free(lessHead);
  free(greaterHead);
  lessHead=greaterHead=NULL;
  return ret;
}