【链表】：必写的四道基础题

🎁个人主页：我们的五年

🔍系列专栏：每日一练

🌷追光的人，终会万丈光芒

目录

 前言：

这篇文章会给大家带来几道经典的单链表题目，这些题目的步骤，可能会在一些难的题目中作为基本步骤，也就是难的题目也会应用到这些思想。

比如：

反转一个单链表，寻找一个单链表的中间节点，找到单链表的倒数第K个节点等。

🏝问题1：反转链表

【LeetCode】链接：. – 力扣（LeetCode）

⛷问题描述：

⛷ 问题分析：

●原链表是：1>2>3>4>5

●我们只需要把2节点指向1，3节点指向2……

●但是最重要的还是把1的next指针置为空，不然还是指向2节点，2节点也是指向1节点，就会形成环，所以我们可以先申请一个头节点为NULL，第1个节点指向NULL，然后2>1,3>2,4>3,5>4

●在循环的过程中，要把pcur指向的next指向前一个节点的指针，如果不做任何操作，就直接把next指向newhead，我们就找不到pcur的下一个节点了，所以要先保存下一个节点的指针，然后再去改变pcur的next指针。

 ⛷代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 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：寻找链表的中间节

【LeetCode】链接:. – 力扣（LeetCode）

 ⛷问题描述：

 ⛷问题分析：

如果我们先去遍历一下链表有多少个元素，然后把个数除以二去寻找中间节点，这样差不多要进行两次遍历，但是我们用快慢指针就能很好的避免这种情况。

⛷代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
        return slow;
}

 🏝问题3：返回单链表的倒数第K个节点的值

【LeetCode】链接:. – 力扣（LeetCode）

⛷问题描述：

⛷问题分析： 

这题我们也可以用快慢指针去解题，我们需要将快慢指针拉开K个节点的距离，然后我们要快慢指针同步往后走，等fast指针走到NULL，此时slow就是倒数第K个节点。

⛷代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
    ListNode* fast=head;
    ListNode* slow=head;
    while(k--)
    {
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow->val;
}

 🏝问题4：合并两个有序链表

【LeetCode】链接：. – 力扣（LeetCode）

 ⛷问题描述：

 ⛷问题分析：

●创建一个头结点，然后要list1和list2区遍历，谁小就放在为节点的尾部，比如list1的节点比list2节点小，我们就可以ptail->list1,然后让list1往后面遍历，直到有一个节点为NULL，我们就跳出循环。

●后面一步我们只要把剩下链表补充到ptail的后面就可以，因为list1和list2是先后遍历，所以list1和list2不可能同时走到NULL，一定有一个先走到NULL，如果是list1先走到NULL，那么我们只要把list2剩余的节点补充到ptail的后面就可以了，即ptail->next=list1。

⛷代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* phead=(ListNode*)malloc(sizeof(ListNode));
    ListNode* ptail=phead;
    while(list1&&list2)
    {
        if(list1->val>list2->val)
        {
            ptail->next=list2;
            ptail=list2;
            list2=list2->next;
        }
        else
        {
            ptail->next=list1;
            ptail=list1;
            list1=list1->next;
        }
    }
    ptail->next=list1==NULL?list2:list1;
    return phead->next;
}

 总结：

这四个题目可以让我们对链表有一个认识，虽然很简单，但是这几个题还是很有用的，可以重点看一下，后期还会继续带来链表较难的题目，可以的铁子可以三连，感谢大家的支持。