【LC刷题系列】【持续更新】链表问题

12次阅读
没有评论

141. 环形链表 判断链表是否存在环 暴力法: 一个指针在链表中步进,元素一个个添加到hashSet中,添加失败的时候 就是出现了重复节点的时候 返回true,因为HashSet有hash算法,所以时间复杂度是O(N),但是空间复杂度是O(N)

    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            boolean neverShowUp = seen.add(head)
            if (!neverShowUp) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

Floyd判圈法(快慢指针法): 利用龟兔赛跑,如果存在环,快节点必定追上慢节点的原理,需要快节点每次步长为2,慢节点步长为1,相遇即是有环。

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

从这个Floyd判圈法可以延伸出来求环的起点的问题/求环长度的问题 环长度:快慢指针相遇后 快指针停止 记录当前位置,慢指针继续走,再次相遇即是环长度。 求环起点:数学问题,利用二者速度差,相遇后,快节点放回起点,两个节点相同速度继续走,会在环的起点处相遇。具体数学推导我也看迷糊啦。 求两个链表是否相交:把两个链表首尾相接,再用Floyd判断法,如果有环一定相交,如果无环一定平行。


203. 移除链表元素 用了递归的方法,这道题特殊的地方在于需要返回头结点,但是头结点有可能被移除,所以创建一个假的节点,把给定链表追在他后面,返回的时候直接返回假节点的next即可。

    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        ListNode fakeNode = new ListNode(val+1);
        fakeNode.next = head;
        ListNode temp = fakeNode;
        while(temp.next!=null){
            if(temp.next.val==val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        return fakeNode.next;
    }
评论(没有评论)