侧边栏壁纸
博主头像
qiuker

常态咸鱼,偶尔动弹

  • 累计撰写 7 篇文章
  • 累计创建 11 个标签
  • 累计收到 0 条评论

面试算法题

qiuker
2022-03-20 / 0 评论 / 0 点赞 / 52 阅读 / 2,191 字

一.链表

1.链表中环的入口节点

子问题:判断链表中是否存在环,要求时间复杂度$O(N)$,空间复杂度$O(1)$

解法:设置两个指针fast和slow,令fast一次性移动一步,slow一次性移动一步。则只要链表中存在环fast和slow一定会在环中相遇。

代码:

    public boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast)
                return true;
        }
        return false;
    }

进阶:给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。时间复杂度要求$O(N)$,空间复杂度要求$O(1)$

解法:

假设经过了x次循环slow和fast相遇,则此时slow走了x步,fast走了2x步。假设环中有n个节点,则fast比slow多走了kn步,即:

$2x = x + kn$

所以,x是n的若干倍。

假设链表的入口节点和链表入口的距离是 y,则 slow 在环中走了 x - y 步。也就是说只要再走 y 步 slow 就会回到链表的入口结点。

我们令fast指针回到链表头,并改变它的速度,让它一次性走一步。则此时fast和slow都距离链表环的入口结点 y 步,当 fast 再次和 slow 相遇的时候,正好位于链表环的入口结点处

代码:

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        boolean hasLoop = false;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                hasLoop=true;
                break;
            }
        }
        if(!hasLoop) return null;
        fast=pHead;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;

2.链表的公共结点

输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。要求空间复杂度$O(1)$,时间复杂度$O(N)$

image.png

解法:

理想情况下,让两个指针向后遍历即可相遇。前提是链表A的头结点到公共结点的距离等于链表B的头结点到公共结点的距离。

image.png

假设面对下面这种情况:

image.png

可以将链表B加到链表A的前面,链表A加到链表B的前面。则此时两个链表头结点到公共结点的距离就相同了,如下:

image.png

这样的做法原理其实就是a+b=b+a

当然在实际操作时不需要复制链表,只要让链表指针走到尾结点后,再移动到另一个链表的头结点即可。

至于两个链表没有公共结点的情况,其实可以视为两个链表相交于null,最后两个链表的遍历指针都为null。

代码:

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         ListNode p1=pHead1;
         ListNode p2=pHead2;
         while(p1!=p2){
             p1=(p1!=null?p1.next:pHead2);
             p2=(p2!=null?p2.next:pHead1);
         }
        return p1;
    }

3.单链表的排序

用$O(NlogN)$的时间复杂度排序链表

我知道的几种$O(NlogN)$排序算法:

  • 插入排序 + 二分优化 :不适用于链表,因为链表不具备数组$O(1)$获取指定元素的能力

  • 选择排序 + 堆优化 : 可以,用Java中的优先队列即可

  • 归并排序

  • 快速排序

** 选择排序 + 堆优化**

堆不必自己手写,可以直接调用PriorityQueue类,但由于牛客中在线编程时无法直接对链表结点类进行修改,所以无法让链表结点类继承Comparable接口;故而只能通过实现比较器Comparator的方式:

class MyComparator implements Comparator<ListNode>{ //实现比较器
    @Override
    public int compare(ListNode o1,ListNode o2){
        return o1.val-o2.val;
    }
}

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        PriorityQueue<ListNode> pq =new PriorityQueue(new MyComparator());
        ListNode p = head;
        while(p!=null){ #将链表中的节点都加入优先队列
            pq.add(p);
            p=p.next;
        }
        ListNode newHead = pq.poll();
        p = newHead;
        while(!pq.isEmpty()){ #依次取出优先队列中的节点
            p.next = pq.poll();
            p = p.next;
        }
        p.next = null;
        return newHead;
    }
}

0

评论区