【基础算法】单链表的OJ练习(3) # 移除链表元素 # 相交链表 #

简介: 【基础算法】单链表的OJ练习(3) # 移除链表元素 # 相交链表 #

前言


本章的OJ练习也是相对简单的,只要能够理解解题的思路,并且依照这个思路能够快速的写出代码,我相信,你的链表水平已经足够了。


对于OJ练习(2) : ->传送门<-。其中两道题都可运用快慢指针的解题思路,这使得两个题都只需要遍历一次链表即可解答。


对于本章,是链表的OJ练习的最后一篇较为简单的章节,后续的OJ练习将会上难度。


移除链表元素


  • 题目链接:->传送门<-
  • 该题目的描述为:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

4a05bdec842247f6880a7795ff2fbb58.png


这里我们采用的方法是在原链表的基础上重新连接节点,将 Node.val == val 的节点跳过不连接。


我们重新定义一个指向新连接的链表的头节点的指针newhead,然后在定义一个用来连接的指针cur,最终连接好后返回newhead即可。


将 Node.val != val 的节点作为新连接的链表的结点 ,如果一开始head为空或者head链表里全是等于val的结点,(初始化newnode = cur = NULL)此时连接操作就不进行,后面返回newnode(一直为NULL)即可。


7d1476b1417d4473b4b8d18daa4dc588.gifb8746f483437434bb5c5d80724e4cd02.gif


下面是代码实现:

struct ListNode* removeElements(struct ListNode* head, int val){
  // cur为对新连接的链表的连接指针,newhead为新连接的链表的指向头节点的指针
    struct ListNode* cur = NULL, * newhead = NULL;
    struct ListNode* tmp = head;
    while (tmp)
    {
        if (tmp->val != val)   // 如果不等于val就连接
        {
            if (newhead == NULL)   // 连接时如果新的头为空,就将该节点作为头节点
            {
                newhead = cur = tmp;
            }
            else      // 正常连接
            {
                cur->next = tmp;
                cur = cur->next;
            }
        }
        tmp = tmp->next;   // 到下一个节点判断
    }
  // 如果head为空或者head链表里面所有节点的val都为所给的val,就说明没有新的头,这里判断是为了防止空指针解引用
  // 如果是正常情况,需要将新连接的最后一个节点的next指向NULL,如果已经指向NULL,多操作一步也没有问题
    if (cur) cur->next = NULL;
    // 最后返回新连接的链表的头
    return newhead;
}



相交链表


  • 题目链接:->传送门<-
  • 该题目描述为:给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null


也就是:


c7d8e3c9004c447d8dbe65d1d787e454.png


1352f662d6a744d183222242026dc40b.png


解题思路一:【长链表先走长度差步】

分别遍历两个链表并求其长度,然后算出两个链表的长度差,让长的那个链表先走长度差步,再一起走,如果有相交节点,最终会同时到达相交的初始节点,返回该节点即可;如果没有相交,最后会同时到达NULL。


79935d913d544f34966b96c7e9c4f09e.gif



55eba11501c2490d9dd70241b3161e03.gif

下面是代码实现:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int count1 = 0, count2 = 0;
    struct ListNode *pa = headA, *pb = headB;
    while (pa) pa = pa->next, count1 ++ ;
    while (pb) pb = pb->next, count2 ++ ;
    int max = count1, min = count2;
    struct ListNode *maxList = headA, *minList = headB;
    if (count1 < count2)
    {
        max = count2;
        min = count1;
        maxList = headB;
        minList = headA;
    }
    int gap = max - min;
    while (gap -- ) maxList = maxList->next;
    while (maxList != minList)
    {
        maxList = maxList->next;
        minList = minList->next;
    }
    return maxList;
}


解题思路二:【双指针直接遍历】


首先我们可以先判断这两个链表是否有一个为空或者都为空,有空的情况那么一定不相交,此时直接返回NULL。


如果两个链表相交,那么从相交的那个起始节点开始,后面的长度是相同的。由此我们定义两个指针pa与pb分别指向headA的头节点与headB的头节点并同时向后遍历链表。


如果pa不为NULL,则移到下一个节点,如果pb不为空,也移到下一个节点。如果第一次遍历pa为空,则将pa指向headB的头节点;如果第一次遍历pb为空,则将pb指向headA的头节点。至于到底相不相交,第二遍遍历会见分晓。


我们假设两个链表相交,那么设从相交的初始节点开始到NULL的长度为n,headA的头节点到相交的初始节点的长度为x,headB的头节点到相交的初始节点的长度为y。按照上一条的思路,当pa第一次遍历到达NULL时,pa一共走了x + n的长度,此时将pa指向headB的头节点;当pb第一次遍历到达NULL时,pb一共走了y + n的长度,此时将pb指向headA的头节点。仔细思考就会发现,pa在headB走到相交的初始节点还需走y的长度,此时pa一共走了x + n + y;pb在headA走到相交的初始节点还需走x的长度,此时pb一共走了y + n + x。这时,pa走的长度与pb走的长度恰好相等,且pa与pb都刚好指向相交的初始节点。所以,该方法能够有效的找出那个相交的初始节点。


82f7d5e3069c4e808b3bae9bde191fb2.gif


如果两个链表不相交,也是一样,通过双指针分别依次向后遍历链表。如果两个链表长度相等,最终pa与pb在第一次遍历的时候就都会到达NULL,此时返回NULL;如果两个链表长度不相等,同样的,在第一次遍历时,只要pa或者pb指向NULL,就将pa或者pb指向另外一个链表的头节点,然后继续遍历。我们假设headA链表的长度为x,headB链表的长度为y,当pa第一次遍历指向NULL时,走的长度为x,此时将pa指向headB的头节点;当pb第一次遍历指向NULL时,走的长度为y,此时将pb指向headA的头节点。不出所料,两个指针在第二次遍历链表时最后同时指向NULL,这是因为,pa在headB的遍历要走的长度为y,此时pa总共走的长度为x + y;pb在headA的遍历要走的长度为x,此时pb总共走的长度为y + x。可以看到,第二次遍历走完两个指针走的长度是相同的,并且两个指针都是指向NULL。所以,两个链表不相交,遍历的两个指针最终都是同时指向NULL。


0bf644be1f484012ad7d31e737ced16c.gif


下面是代码实现:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    // 如果其中有一个链表为空或者全为空,说明不可能相交,直接返回NULL
    if(headA == NULL || headB == NULL) return NULL;
    struct ListNode* pa = headA, * pb = headB;
    // 对于headA与headB只有相交与不相交的情况
    // 相交则跳出循环
    // 不相交则再循环里面就返回
    // pa == pb说明找到相交的初始节点了,条件判断为假,跳出循环
    while (pa != pb)
    {
        // 同步向后遍历
        pa = pa->next;
        pb = pb->next;
        // 如果两个指针都指向空,说明headA与headB不相交
        if (pa == NULL && pb == NULL) return NULL;
        // 如果pa遍历完headA就到headB继续遍历
        if (pa == NULL) pa = headB;
        // 如果pb遍历完headB就到headA继续遍历
        if (pb == NULL) pb = headA;
    }   
    // 这里返回pa或者pb都是可以的,都指向相交的那个初始节点
    return pa;
}


写在最后


对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。


感谢阅读本小白的博客,错误的地方请严厉指出噢!


相关文章
|
2月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
47 3
|
4月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
2月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
36 4
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
18 1
|
3月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
5月前
【数据结构OJ题】环形链表
力扣题目——环形链表
38 3
【数据结构OJ题】环形链表
|
5月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
54 1
【数据结构OJ题】复制带随机指针的链表
|
5月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
32 1
【数据结构OJ题】环形链表II
|
4月前
|
算法 C++ Windows
空间射线与三角形相交算法的两种实现
空间射线与三角形相交算法的两种实现
44 0