链表中的倒数第k个结点 合并两个链表 分割链表 链表的回文结构

简介: 链表中的倒数第k个结点 合并两个链表 分割链表 链表的回文结构

一、链表中倒数第k个结点


题目来源于:牛客网->题目链接


题目描述:


输入一个链表,输出该链表中倒数第k个结点。


示例:


输入:1,{1,2,3,4,5}


返回值:{5}


解题思路:


  1. 创建两个指针:


①:返回指针:ret.


②:后指针:tail


  1. 后指针(tail),将该指针先走k-1步.


  1. 两个指针同时走,当后指针走向最后一个结点时,ret刚好走到倒数第k个位置.


特殊情况:


pListHead=NULL和K不合法.



struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if(pListHead==NULL||(k<=0))//如果为空链表或者k是<=0,直接返回NULL
    {
        return NULL;
    }
    struct ListNode*ret=pListHead;
    struct ListNode*tail=pListHead;
    //后指针先走k-1步
    while((--k)&&tail)//细节,k--和--k的区别
    {
        tail=tail->next;
    }
    //k太大
    if (tail == NULL)//如果指向的就是最后一个节点的后的NULL,即k太大
    {
        return NULL;
    }
    //两个指针一起走
    while(tail->next!=NULL)
    {
        tail=tail->next;
        ret=ret->next;
    }
    return ret;
}


二、合并两个有序链表


题目来源于:力扣->题目链接


题目描述:


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


示例1:


输入:


l1 = [1,2,4], l2 = [1,3,4]


输出:


[1,1,2,3,4,4]


解题思路:


 可以创建一个头结点,头结点在链表为空等特殊情况时不需要调整头指针,因为即使链表为空,也还有头结点,只需要将头结点的next置空即可.


步骤:


  1. 创建头结点,并初始化头结点的next为NULL.


  1. 由于头结点的指针域(next)需要作为函数的返回值,所以需要再创建一个指针记录头结点.


  1. 只需要分别比较这两个链表的值,谁小谁尾插到新链表,直到一方为空.


  1. 将此时不为空的链表尾插到新链表.


  1. 返回头结点的next;


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //创建带哨兵卫的结点
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    phead->next = NULL;
    struct ListNode* ret = phead;//保存这个哨兵卫结点
    while (list1 && list2)
    {
        if (list1->val < list2->val)//谁小谁尾插
        {
            phead->next = list1;
            phead = phead->next;
            list1=list1->next;
        }
        else
        {
            phead->next = list2;
            phead = phead->next;
            list2=list2->next;
        }
    }
    //如果一方为空的情况
    if (list1 == NULL)
    {
        phead->next = list2;
    }
    if (list2 == NULL)
    {
        phead->next = list1;
    }
    return ret->next;//哨兵卫结点的next
}

三、分割链表


题目来源于:牛客网->题目链接


题目描述:


  现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。


示例:



解题思路:


  1. 创建两个带头结点的单链表.


①:SmallHead:用于保存比目标值小的结点.


②:BigHead:用于保存比目标值大的结点.


  1. 由于后面要返回新链表,并且小链表的尾巴要与大链表的头链接,综上,上面的两个头结点不能轻易改变,老样子创建两个指针代替它们遍历.


①:SmallTail


②:BigTail


  1. 遍历原链表,依次与目标值x比较:


小于目标值x尾插入SmallHead小链表.


大于等于==目标值x,尾插入BigHead大链表.


  1. 将小链表与大链表链接起来.


注意:这里需要注意的是大链表(BigHead)的尾结点不一定是原有链表的尾结点,即大链表(BigHead)的尾结点不一定为NULL,我们要手动设置为NULL,否则链表无法结束.


  1. 最后:由于头结点是自己用malloc手动申请的,c语言阶段,需要我们自己手动释放,释放前记得保存要返回的头指针哦.


图解:


特殊情况:



代码:


class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
    //创建两个链表的头结点
    ListNode* SmallHead=(ListNode*)malloc(sizeof(ListNode));
    ListNode* BigHead=(ListNode*)malloc(sizeof(ListNode));
    //代替两个头结点遍历的指针
    ListNode* SmallTail= SmallHead;
    ListNode* BigTail= BigHead;
    //遍历现有链表
    while(pHead)
    {
        //小的尾插到小的链表中
        if(pHead->val<x)
        {
            SmallTail->next=pHead;
            SmallTail=SmallTail->next;
        }
        else {//大的尾插到大的链表中
            BigTail->next=pHead;
            BigTail=BigTail->next;
        }
        pHead=pHead->next;
    }
    //链接
    SmallTail->next=BigHead->next;
    //大链表的尾结点不一定是NULL,我们要置NULL
    BigTail->next=NULL;
    //保留要返回的头指针
    pHead=SmallHead->next;
    //释放自己动态内存申请的空间
    free(SmallHead);
    free(BigHead);
    return pHead;
    }
};


四、链表的回文结构


题目来源于:牛客网->题目链接


题目描述:


对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构(从前往后,和从后往前遍历结果一样)。


给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。


示例1:


输入:


1->2->2->1


输出;


true


示例2:


输入:


1->2->3->2->1


输出:


true


解题思路:


将链表的后半段逆序,然后与前半段一次比较,都一样则是回文结构,不一样则不是回文结构.


  1. 寻找中间结点,前面牛牛讲过方法哦,快慢指针就行.


  1. 从中间结点开始,反转原链表的后半段.


  1. 比较链表的前半段与后半段:


不相同:则返回false


相同:则返回true


链表中间结点与链表逆置在这篇文章->传送门


图解:



代码:


class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
       //寻找中间结点
        ListNode* mid=middleNode(A);
        //反转链表后半段
        ListNode* B=reverseList(mid);
        //比较
        while(A&&B)
        {
            if(A->val!=B->val)
            {
                return false;
            }
            A=A->next;
            B=B->next;
        }
        return true;
    }
};
目录
相关文章
|
27天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
58 1
|
9天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
8 1
|
29天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
38 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
23天前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
40 0
|
29天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
14 0
|
1月前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
25 0
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
5月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
5月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
48 2