美文网首页
LeetCode 刷题记录 2020

LeetCode 刷题记录 2020

作者: stbtk | 来源:发表于2020-02-13 00:22 被阅读0次

    2020.02.10

    2020年计划刷 LeetCode 题目 50 道,差不多一周一道题的进度,直到今天,2020年2月10日,我还有刷一道题……

    [TOC]

    1. LeetCode 21, 83, 141 Easy Linked List

    21. Merge Two Sorted List

    ​ Difficulty: Easy, Tag: Linked List

    Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

    Example:

    Input: 1->2->4, 1->3->4
    Output: 1->1->2->3->4->4
    

    这个没有任何要点,算练手,不算在这50题里面,所以也就不用多说,直接上代码。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            
            ListNode head = new ListNode(0);
            ListNode p = head;
            
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    p.next = l1;
                    p = p.next;
                    l1 = l1.next;
                } else {
                    p.next = l2;
                    p = p.next;
                    l2 = l2.next;
                }
            }
            
            if (l1 == null)
                p.next = l2;
            else
                p.next = l1;
            
            return head.next;
            
        }
    }
    

    83. Remove Duplicates from Sorted List

    Given a sorted linked list, delete all duplicates such that each element appear only once.

    Example 1:

    Input: 1->1->2
    Output: 1->2
    

    Example 2:

    Input: 1->1->2->3->3
    Output: 1->2->3
    

    这个也没什么好说的,既然是有序的,就遍历链表,和前一个值做对比,相等就删除就可以了。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null) 
                return head;
            
            int val = head.val;
            ListNode p = head;
            while (p.next != null) {
                if (p.next.val == val)
                    delete(p.next, p);
                else {
                    p = p.next;
                    val = p.val;
                }
            }
            
            return head;
        }
        
        private void delete(ListNode node, ListNode pre) {
            pre.next = node.next;
        }
    }
    

    LeetCode 网站给出的解:

    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }
    

    141. Linked List Cycle

    Given a linked list, determine if it has a cycle in it.

    To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

    Example 1:

    Input: head = [3,2,0,-4], pos = 1
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the second node.
    
    img

    Example 2:

    Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the first node.
    
    img

    Example 3:

    Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.
    
    img

    Follow up:

    Can you solve it using O(1) (i.e. constant) memory?

    第一个思路:利用集合

    遍历链表,判断当前结点是否已经存在集合中,存在的话说明有环,否则将结点加入集合。

    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     LitNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null)
                return false;
            
            Set<ListNode> s = new HashSet<ListNode>();
            ListNode p = head;
            while (p != null) {
                if (s.contains(p))
                    return true;
                
                s.add(p);
                p = p.next;
            }
            
            return false;
        }
    }
    

    时间复杂度:O(1), 空间复杂度: O(n)

    方法二:双指针

    fast(步长为2) & slow(步长为1),如果存在环,fast 和 slow 始终不会指向空指针并且 fast 最终会和slow 指向同一个结点。

    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     LitNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null)
                return false;
            
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null) {
                if (fast == slow)
                    return true;
                
                slow = slow.next;
                fast = fast.next.next;
            }
            
            return false;
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode 刷题记录 2020

          本文链接:https://www.haomeiwen.com/subject/vcezxhtx.html