【单链表经典习题讲解】

大家好呀，今天向大家分享的是关于单链表的一些比较基础且经典的题目，相信你看完了一定会对单链表的知识掌握的更加熟练。

1 移除链表元素

2 反转链表

3 链表的中间结点

1 移除链表元素

题目描述：

解题思路：

遍历链表，用cur表示当前位置，记录要去除元素的前一位地址（prev），让prev->next=cur->next.然后不断迭代，直至cur为空.

但是要额外处理当第一个元素就是要去除元素这种情况。

具体代码实现：


struct ListNode* removeElements(struct ListNode* head, int val)
{
  struct ListNode* prev=NULL;
  struct ListNode* cur=head;
  while(cur)
   {
    if(cur->val == val)
      {
        //头删
        if(cur == head)
        {
            head=cur->next;
            free(cur);
            cur=head;
        }
        else
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
        }
        
      }
    else
    {
        prev=cur;
        cur=cur->next;
    }
}
return head;
}

结果展示：

2 反转链表

题目描述：

解题思路1：

遍历链表，让cur指向当前位置，记录cur前一位的位置prev,记录cur后一位位置next,让cur->next=prev,将prev=cur,cur=next,next=next->next,然后不断迭代，结束条件是cur为NULL，但是要注意当next为NULL时就不要进行next=next->next。

具体代码：


 ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return head;
    }
struct ListNode* prev=NULL;
struct ListNode* cur=head;
struct ListNode* next=head->next;
 
while(cur)
{
    //翻转
    cur->next=prev;
 
    prev=cur;
    cur=next;
    if(next)
    {
        next=next->next;
    }
 
}
return prev;
}

结果展示：

解题思路2：

遍历链表，将链表中的元素头插到一个新链表的头上，然后迭代下去，直到cur为NULL，但是要注意保存cur的下一个位置。

具体代码：


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

结果展示：

两种方法都是可行的，具体用哪一种可以自己选择，但是不要刻意去关注leetcode结果展示中的执行用时和内存消耗，这可能与网速有关。

3 链表的中间结点

题目描述：

解题思路：

常规思路：遍历链表求链表长度，然后再遍历一遍数组求中间结点

具体代码：


struct ListNode* middleNode(struct ListNode* head)
{
int count=0;
struct ListNode* cur=head;
while(cur)
{
    count++;
    cur=cur->next;
}
 cur=head;
 int i=0;
 for(i=0;i2;i++)
 {
     cur=cur->next;
 }
return cur;
}

这种方法可行，但是有没有其他方法只遍历一遍链表呢？

快慢指针：让slow一次走一步，fast一次走两步，直到fast或者fast->next为NULL时结束，此时slow就是中间结点。

具体代码：


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

结果展示：

4 链表中倒数第k个结点

题目描述：

解题思路：

仍然用快慢指针解题，让快指针先走k步，然后同时走。

具体代码：


struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    
    struct ListNode* slow=pListHead;
    struct ListNode* fast=pListHead;
    while(k--)
    {
        if(!fast)
            return NULL;
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
    
}

其中值得注意的是当fast先走时并且当fast为空时直接返回NULL。

结果展示：

5 合并两个有序链表

题目描述：

解题思路1：

不创建头结点，一一遍历两个链表，将较小的值拿下来尾插，然后迭代下去，直至其中一个链表为空，然后把另外一个链表剩下的结点全部链接。但是要注意考虑头为NULL的特殊情况。

具体代码：


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
if(list1==NULL)
{
    return list2;
}
if(list2==NULL)
{
    return list1;
}
while(list1 && list2)
{
    if(list1->val < list2->val)
    {
       if(head==NULL)
       {
           tail=head=list1;
       }
       else
       {
            tail->next=list1;
            tail=tail->next;
       }
       list1=list1->next;
    }
 
    else
    {
       if(head==NULL)
       {
           tail=head=list2;
       }
       else
       {
            tail->next=list2;
            tail=tail->next;
       }
       list2=list2->next;
    }
}
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head;
    
}

结果展示：

解题思路2：

创建一个头结点，不存储数据，方法与第一种类似，但是不需要考虑头为NULL的情况。

具体代码：


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL)
{
    return list2;
}
if(list2==NULL)
{
    return list1;
}
struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail=head;
 
 
while(list1 && list2)
{
    if(list1->val < list2->val)
    {
       tail->next=list1;
       tail=tail->next;
       list1=list1->next;
    }
 
    else
    {
       tail->next=list2;
       tail=tail->next;
       list2=list2->next;
    }
}
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    struct ListNode* first=head->next;
    free(head);
    return first;
    
}

结果展示：

这两种方法都是可行的，我个人更喜欢第二种方法。

6 链表分割

题目描述：

解题思路：

创建两个头结点分别连接=x的链表，最后将较小链表的尾连接到大链表的头的下一位，最后别忘了给大链表的尾置NULL。

具体代码：


class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode*headSmall=(ListNode*)malloc(sizeof(ListNode));
        ListNode*tailSmall=headSmall;
        ListNode*headBig=(ListNode*)malloc(sizeof(ListNode));
        ListNode*tailBig=headBig;
        ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                tailSmall->next=cur;
                tailSmall=cur;
                
            }
            else
            {
                tailBig->next=cur;
                tailBig=cur;
            }
            cur=cur->next;
        }
        
        tailSmall->next=headBig->next;
        tailBig->next=NULL;
        return headSmall->next;
    }
};

结果展示：

7 链表的回文结构

题目描述：

解题思路：

将链表看作两部分，前半部分和后半部分，再将后半部分逆置一一与前半部分比较，若相等就返回true,否则返回false.这里就不需要将前半部分的尾置为NULL。

具体代码：


struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow=head;
    struct ListNode* quick=head;
 
    while(quick && quick->next)
    {
        slow=slow->next;
        quick=quick->next->next;
    }
    return slow;
}
 
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newhead=NULL;
 
    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next=newhead;
        newhead=cur;
 
        cur=next;
 
    }
    return newhead;
}
 
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* mid=NULL;
        mid=middleNode(A);
      ListNode* reverse=reverseList(mid);
        while(A && reverse)
        {
            if(A->val != reverse->val)
            {
                return false;
            }
            A=A->next;
            reverse=reverse->next;
        }
        return true;
    }
};

结果展示：

8 相交链表

题目描述：

解题思路：

常规思路是遍历其中一个链表，再将该链表与另外一个链表中每个结点比较，这样做时间复杂度为O(N^2),显然是不符合题意的。较为优的解题思路是先判断链表是否相交，然后求链表长度差值，让较长的链表先走差值步，再同时走，直到两个结点相等。

具体代码：


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *tailA=headA,*tailB=headB;
    int lenA=1;
    int lenB=1;
    while(tailA->next)
    {
        lenA++;
        tailA=tailA->next;
    }
    while(tailB->next)
    {
        lenB++;
        tailB=tailB->next;
    }
    if(tailA!=tailB)
    {
        return NULL;
    }
    int dis=fabs(lenA-lenB);
    struct ListNode *small=headB;
    struct ListNode *big=headA;
    if(lenA
    {
        small=headA;
        big=headB;
    }
    while(dis--)
    {
       big=big->next; 
    }
    while(big!=small)
    {
        big=big->next;
        small=small->next;
    }
    return small;
}

结果展示：

9 环形链表

题目描述：

解题思路：

定义两个快慢指针，让慢指针一次走一步，快指针一次走两步，当快指针等于慢指针时就返回true,否则返回false.

具体代码：


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(fast==slow)
       {
           return true;
       }
    }
    return false;
}

结果展示：

题后深究：

1 slow一次走一步，fast一次走两步，他们一定会相遇吗？

2 若是slow一次走一步，fast一次走三步会怎样？fast一次走4步会怎样？

假设slow刚进环时slow与fast之间的距离为X，由于fast每次都比slow快一步，所以他们之间的相对距离在以1之间减少，所以肯定会相遇。

如果fast一次走三步，当X为偶数时，他们一定相遇，当X为奇数时fast肯定在某个情况会恰好超过slow一位，这个时候他们能否相遇取决于C-1的奇偶情况（C表示环的长度），当C-1为奇数时永远不会相遇，当C-1为偶数时会相遇。

当fast一次走四步时也是同样的分析方法。

10 环形链表

题目描述：

解题思路：

一个指针从相遇点开始走，一个指针从表头开始走，它们会在环的入口点相遇。

代码实现：


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

结果展示：

题后深究：

为什么一个指针从相遇点开始走，一个指针从表头开始走，它们会在环的入口点相遇？

由图中公式可知，上述结论是成立的。

相关阅读:
Linux命令行
 一起Talk Android吧（第四百二十一回：绘图中添加阴影）
GD32F303固件库开发（10）----双ADC轮询模式扫描多个通道
 【Qt 按钮】QPushButton所有函数和样式
 左支座零件的机械加工工艺规程及工艺装备设计【计算机辅助设计与制造CAD】
Go 语言数组基础教程 - 数组的声明、初始化和使用方法
 男孩姓洪取什么名字好听
 【LeetCode19. 删除链表的倒数第 N 个结点】——链表，快慢双指针，虚拟头结点、利用栈
 信息学奥赛一本通：1310：【例2.2】车厢重组
 【会员管理系统】篇二之项目搭建、初始化、安装第三方库
原文地址：https://blog.csdn.net/m0_68872612/article/details/126237995