数据结构——链表OJ题

目录

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

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

3.变形题：找到链表中倒数第k个节点

4.经典题：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

结语

个人主页：大耳朵土土垚-CSDN博客

所属专栏：数据结构学习笔记

1.给你一个链表的头节点 

head

 和一个整数 

val

 ，请你删除链表中所有满足 

Node.val == val

 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

解题思路：

创建指针遍历链表找到对应节点删除；

创建两个指针变量cur和pre用来记录，cur表示当前遍历的节点，pre表示上一个节点如图所示

不要忘了有两种情况，当第一个节点就是对应节点时需要将头指针head改变 ；

如果忘记第一种情况就会发现以下示例：

图中null就是指pre为空指针的情况；

以下是完整代码实现： 

struct ListNode {
    int val;
    struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* pre = NULL;
    while (cur)
    {
        if (cur->val == val)//找到val值相同的节点时
        {
            if (pre == NULL)//如果是第一个节点，也就是图中第②种
            {
                cur = head->next;
                free(head);
                head = cur;
            }
            else//其他情况
            {
                pre->next = cur->next;
                free(cur);
                cur = pre->next;
            }
        }
        else//不相同时
        {
            pre = cur;
            cur = cur->next;
        }
    }
    return head;
}

另外一种思路：

遍历链表，把不是val节点拿出来尾插，这里就不细讲有兴趣的可以打在评论区或私信我哦~

代码如下：

struct ListNode {
    int val;
    struct ListNode* next;
    
};
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;
    while (cur)
    {
        if (cur->val != val)
        {
            if (newhead == NULL)
            {
                tail = cur;
                newhead = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
            tail->next = NULL;        }
        else
        {
            struct ListNode* pos = cur;
            cur = cur->next;
            free(pos);
        }
    }    return newhead;
}

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

解题思路：

给fast，slow两个指针，fast走两步，slow走一步 ,当fast走到尾时，slow恰好走到中间。

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

3.变形题：找到链表中倒数第k个节点

解题思路：

还是快慢指针，只要fast与slow之间距离为k，那么当fast走到终点时，slow所在的节点就是倒数第k个节点

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
struct ListNode* fast = pListHead,*slow = pListHead;
 for(int i = 0; i < k; i++)//先让fast走k步
    {
        if(fast == NULL)//如果k大于链表长度记得要及时返回哦
         return NULL;
        fast = fast->next;
    
    }
while(fast)
{
   
    fast = fast->next;
    slow = slow->next;
}
return slow;
}

先让fast走k步拉开距离，然后fast与slow一起走，当fast为空指针时，slow即为倒数第k个节点；

4.经典题：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路：

    取小的尾插

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {    struct ListNode* head = NULL,*tail = NULL;
     if(list1 == NULL)//注意有链表为空的情况，直接返回另一个链表
        return list2;
    if(list2 == NULL)
        return list1;
    while(list1 && list2)//注意这里是一个链表结束就都结束，所以两个都要为真用&&
    {
     if(list1->val <= list2->val)
     {
         if(head == NULL)
         {
             head = tail = list1;
         }
         else
         {
             tail->next = list1;
             tail = tail->next;
         }
         list1= list1->next;
     }
     else
     {  if(head == NULL)
         {
             head = tail = list2;
         }
         else
         {
             tail->next = list2;
             tail = tail->next;
         }
         list2= list2->next;
     }
    }
    if(list1 == NULL)
    {
        tail->next = list2;
    }
    else
    {
        tail->next = list1;
    }
    return head;
}

 要注意当有链表为空的情况，以及取小结束后的情况；

结语

链表尾插，我们可以用一个tail指针来记录尾插后的节点，尾插直接在tail节点后即可，这样就不用每次尾插都循环遍历，大大减少了时间复杂度 ，提高了运行效率。大家如果有什么问题或者想法欢迎打在评论区或私信我哦~