力扣牛客之十大链表必刷题

【声明】:由于笔者水平有限,在今后的博文中难免会出现错误和不准之处,本人也非常渴望知道这些错误,恳请读者批评斧正,期待您的留言评论。

文章目录 

目录

文章目录 

唠叨一下:做数据结构题目时不论难易,一定要画图理解,包括后期发布的递归也是这样,千万千万不能懒惰哦!

一、十大链表必刷题有哪些?

二、算法分析及代码示例

1.反转链表(剑指offer)

2.找到链表的中间节点

3.找出单链表中倒数第k个节点(剑指offer)

4.链表分割:所有小于x的节点排在大于等于x的节点之前(字节跳动笔试题)

5.删除已经排好序的链表中重复的节点(字节跳动笔试题)

6.链表的回文结构(腾讯笔试题)

7.环形链表I:判断链表是否有环(百度笔试题)

8.环形链表II:找入口节点(腾讯笔试题)

9.相交链表(剑指offer)

10.合并两个有序的链表(剑指offer)

11.删除所有关键字为key的节点(剑指offer)

总结

唠叨一下:做数据结构题目时不论难易,一定要画图理解,包括后期发布的递归也是这样,千万千万不能懒惰哦!
 

一、十大链表必刷题有哪些?

1、反转链表
2、找到链表的中间节点
3、找到链表中倒数第k个节点
4、链表分割,所有小于某个数的节点都放在大于或者等于那个数的节点之前
5、删除已经排好序的链表中重复的节点
6、链表的回文结构
7、环形链表I:判断链表是否有环
8、环形链表II:找入口节点
9、相交链表:找到两个链表相交的起始节点
10、合并两个已排好序的链表
11、删除所有出现关键字为key的节点(嘻嘻,你不会真的天真的以为只有十题吧..)

二、算法分析及代码示例

//无头单向非循环链表
class Node {
    //实例成员没有初始化,默认值为对应的0值,引用类型默认为null,简单类型默认为0
    public int data;//数值域---0
    public Node next;//下一个节点的引用---null

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

 

1.反转链表(剑指offer)

思路:有两种方法:一是直接翻方向,二是利用头插法,因为该题比较简单,直接看代码示例就能理解,不过在这里,笔者要再强调一遍的是,不管多简单的题目,一定要画图理解,千万不能眼高手低!!!

代码如下(示例):

    //1、反转链表
    //方法一:直接翻方向(最好掌握这个方法,因为在后面的“回文结构”中也用到了这个方法)
    public Node reverseList(Node head) {
        Node prev = null;//需要反转的节点的前驱
        Node cur = head;//需要反转的节点
        Node newHead = null;//反转后的单链表的头
    //遍历链表
        while(cur != null) {
            Node curNext = cur.next;//需要反转的节点的后继
            if(curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }
    //方法二:头插法(取原链表的节点,头插到新链表)(相对于直接翻方向容易理解一些)
    public Node reverseList1(Node head) {
        Node cur = head;//进行头插的节点
        Node newHead = null;
        while(cur != null) {
            Node curNext = cur.next;//进行头插的节点的后继
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        return newHead;
    }

 

2.找到链表的中间节点

NB(注意):如果有两个中间节点,则返回第二个

思路:利用快慢指针fast和slow,两个都从头开始走,fast一次走两步,slow一次走一步,当fast == null || fast.next == null 时,slow就是中间结点

代码如下(示例):

    public Node middleNode(Node head) {
        Node slow = head;
        Node fast = head;
        //只要fast或者fast.next有一个为空,那么肯定走到尾了,注意别忘记加上fast.next!=null
        //注意不能写成fast.next != null && fast != null这样,因为fast走两步后可能为空了,再执行 
        //循环fast.next可能会导致空指针异常
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

3.找出单链表中倒数第k个节点(剑指offer)

思路:还是利用快慢指针fast和slow,fast先走k-1步,然后fast和slow每个同时走一步,当fast.next==null时,slow就是所求

    public Node FindKthToTail(Node head, int k) {
        //单链表不能为空
        if(head == null) {
            return null;
        }
        //先判断k的合法性
        //此处为了只需一次遍历单链表就能解决问题,同时也为了提高时间效率,没有加上k > size()这个 
        //条件,所以后面要注意空指针异常(第一个while循环做了处理),size()实际上是我写的求单链表 
        //长度的方法,在此你只要将k > size()理解成"k > 单链表的长度"即可
        if(k <= 0) {
            System.out.println("k不合法!");
            return null;
        }
        Node slow = head;
        Node fast = head;
        //不能让它一直往后面走,可能会导致空指针异常
        while(k - 1 > 0) {
            //设置fast.next != null这个条件就是防止k大于单链表的长度
            if(fast.next != null) {
                fast = fast.next;
                k--;
            }else {
                System.out.println("没有这个节点!");
                return null;
            }
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

4.链表分割:所有小于x的节点排在大于等于x的节点之前(字节跳动笔试题)

NB:链表分割以后需要保证原来的数据顺序不变—–所以采用“尾插法”

思路:

  1. 设置两个线段的开始还有结束,分别是bs,be,as,ae
  2. 定义一个cur,遍历原来的单链表
  3. 如果cur.data < x,就放到第一个线段,反之,放到第二个线段,注意,为了保证分割链表以后原来的数据顺序不变,此处采用“尾插法”,需要注意的是,一定要判断是不是第一次插入数据,因为第一次和其他次插入数据所执行的操作是不一样的
  4. cur == null时,原来的单链表就遍历完了
    public Node partition(Node head, int x) {
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = head;
        while (cur != null) {
            if (cur.data < x) {
                //第一次插入(bs为空时)
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            } else {
                //第一次插入(as为空时)
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //1、判断bs是否为空,如果bs == null,返回as
        if (bs == null) {
            return as;
        }
        //2、如果bs不为空,需要进行拼接
        be.next = as;
        //3、如果ae不为空,ae.next需要置为空
        if (ae != null) {
            ae.next = null;
        }
        return bs;
    }

5.删除已经排好序的链表中重复的节点(字节跳动笔试题)

注意:1、已经排好序的链表就意味着重复的节点集中在一起,读题时就要联想到这一点

           2、该题是将重复的节点全部删除干净

思路:定义一个虚拟节点来解决问题(也就是将没有重复出现的节点放到一个新的链表当中)

    public Node deleteDuplication(Node head) {
        Node cur = head;
        Node newHead = new Node(-1);//定义的虚拟节点
        Node tmp = newHead;
        while(cur != null) {
            //一定要加上cur.next != null这个条件,防止一直朝后走导致空指针异常(因为后面要判断 
            //cur.data == cur.next.data,涉及cur.next,所以要多想一下)
            if(cur.next != null && cur.data == cur.next.data) {
                while(cur.next != null && cur.data == cur.next.data) {
                    cur = cur.next;
                }
                cur = cur.next;//多走一步(因为要把重复的节点全部删除掉)
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;//最后一定不要忘记了将尾结点的next置为空
        return newHead.next;
    }

6.链表的回文结构(腾讯笔试题)

注意:用到了前面的反转链表和找链表的中间节点这两个方法的算法思想

思路:1、找到中间节点

           2、翻转链表后半部分的节点

           3、先从奇数个节点入手,最后再考虑偶数个节点的情况

    public boolean chkPalindrome(Node head) {
        //单链表为空,肯定不是回文结构
        if(this == null) {
            return false;
        }
        //只有头结点自己,肯定是回文结构
        if(head.next == null) {
            return true;
        }
        //1、找到单链表的中间节点
        Node fast = head;
        Node slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //2、开始反转单链表的后半部分   slow肯定在中间位置
        Node cur = slow.next;
        while(cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //slow是最后的节点了
        //3、开始一个从头走,一个从尾走
        while(slow != head) {
            if(slow.data != head.data) {
                return false;
            }
            //判断偶数的情况(一定要注意的是不能比较的是元素大小!!!)
            if(head.next == slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

7.环形链表I:判断链表是否有环(百度笔试题)

思路:本题很简单,利用快慢指针做即可

    public boolean hasCycle(Node head) {
        Node fast = head;
        Node slow = head;
        //如果有环,必然不会存在null
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

8.环形链表II:找入口节点(腾讯笔试题)

思路:1、设环的长度为C,相遇时fast走了N圈,从头到入口点的距离为X,入口点到相遇点为Y;

           2、如果有环,fast和slow相遇的时候,fast走的路程是slow的两倍,2 * (X + Y) = X  + NC                    + Y—–>X + Y = NC—–>X = NC – Y

           3、NC是一个定值,当N == 1时,相遇点到入口点的距离就是X,此时使用两个引用,一个                   从头开始走,一个从相遇点开始走,当二者相遇的时候就是入口点

    public Node detectCycle(Node head) {
        Node fast = head;
        Node slow = head;
        //如果有环,必然不会存在null
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        //相遇后,即有环,此时使用两个引用,一个从头开始走,一个从相遇点(此时的slow和fast就在相 
        //遇点)开始走,当二者相遇的时候就是入口点
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

9.相交链表(剑指offer)

思路:1、求两条单链表的长度

           2、计算两条单链表的差值

           3、让长的链表先走差值步,后面详细步骤见代码块即可求出两链表第一次相交节点

    public Node getIntersectionNode(Node headA, Node headB) {
        //1、求长度,走差值步
        int lenA = 0;
        int lenB = 0;
        Node pl = headA;
        Node ps = headB;
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        //注意此时pl,ps位置不再是头了,需要人为设置
        pl = headA;
        ps = headB;
        //len要放到这个位置计算,最基本的都忘记了!!!
        int len = lenA - lenB;
        //保证pl里面放的是长链表,ps里面放的是短链表
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //长的链表走差步值
        for(int i = 0; i < len; i++) {
            pl = pl.next;
        }

        //2、ps和pl一定在同一个起跑线上
        //设置ps != pl这个条件就是为了相交的时候停下来
        //别忘了pl != null && ps !=null 这个条件,其实也可以省去,因为两链表剩下的节点一样长!
        while(ps != pl && pl != null && ps != null) {
            ps = ps.next;
            pl = pl.next;
        }
        //二者相等也可能是两条链表都为空了
        if(pl == ps && pl != null) {
            return pl;
        }
        return null;
    }

10.合并两个有序的链表(剑指offer)

思路:利用虚拟节点即可

    public Node mergeTwoLists(Node headA, Node headB) {
        //开辟一个虚拟节点
        Node newHead = new Node(-1);
        Node tmp = newHead;
        while(headA != null && headB != null) {
            if(headA.data < headB.data) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if(headA != null) {
            tmp.next = headA;
        }
        if(headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }

11.删除所有关键字为key的节点(剑指offer)

思路:本题比较简单,但是最后别忘记了要回过头来判断第一个节点

    public void removeAllKey(Node head, int key) {
        //单链表为空时
        if(head == null) {
            return;
        }
        //需要注意的是始终要保证prev是cur的前驱
        Node prev = head;
        Node cur = head.next;//代表要删除的节点
        while(cur != null) {
            if(cur.data == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后再判断首节点
        if(head.data == key) {
            head = head.next;
        }
    }

总结

与其说它是十大链表必刷题,不如把“十大”改成“十类”,因为LeetCode和牛客网等刷题网站上面至少80%的题目都是这十类题目本身,或是其变形形式,中心算法思想是一致的,稍稍改动即可,不过若要会做变形形式,首先需要将这些最基本的原题烂熟于心,数据结构的重要性不用说大家都明白,链表在数据结构中也是举足轻重的。

《力扣牛客之十大链表必刷题》

 

可能我们在听老师讲课的时候,或者就拿上面的代码举例吧,我们听或者看的时候,能听懂也能看懂,但是到自己实现起来就不是那么一回事了,笔者本人也是这样,究其原因呢,还是题目刷少了,代码量跟不上!所以平时要多练习,笔者自己呢,也是刚刚开始刷LeetCode没多长时间,希望与大家共同进步。

此处需要敲黑板——若要真正掌握上面的题目,我们最起码要练习五遍以上,而且每一遍都要画图理解,包括之后即将发布的递归也是这样,我们处在一个非常美好的时代,时不我待,万万不能懒惰呀铁子们,我自己也是!

《力扣牛客之十大链表必刷题》

 

还有还有,感谢铁子们能看到最后,蟹蟹啦!

    原文作者:安然无虞
    原文地址: https://blog.csdn.net/weixin_57544072/article/details/120759287
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞