MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 547 Reading time ≈ 1 mins.

Question

Given the head of a linked list, remove the nth node from the end of the list and return its head.

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy, second = dummy;
        for (int i = 1; i <= n+1; i++)
            first = first.next;
        while(first != null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 693 Reading time ≈ 1 mins.

Question

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        while(cur != null && cur.next != null){
            if(cur.val == cur.next.val){
                int temp = cur.val;
                while(cur != null && temp == cur.val) cur = cur.next;
                pre.next = cur;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 488 Reading time ≈ 1 mins.

Question

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null){
            while(cur.next != null && cur.val == cur.next.val)
                cur.next = cur.next.next;
            cur = cur.next;
        }
        return head;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 488 Reading time ≈ 1 mins.

Question

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null){
            while(cur.next != null && cur.val == cur.next.val)
                cur.next = cur.next.next;
            cur = cur.next;
        }
        return head;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 514 Reading time ≈ 1 mins.

Question

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

https://leetcode.com/problems/remove-linked-list-elements/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null){
            if(cur.next.val == val) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return dummy.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 762 Reading time ≈ 1 mins.

Question

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

https://leetcode.com/problems/find-the-duplicate-number/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findDuplicate(int[] nums) {
        //Set<Integer> seen = new HashSet<>();
        //for(int num : nums)
        //    if(!seen.add(num)) return num;
        //return -1;
        int slow = nums[0], fast = nums[0];
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast){
                fast = nums[0];
                while(fast != slow){
                    slow = nums[slow];
                    fast = nums[fast];
                }
                return slow;
            }
        }
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 818 Reading time ≈ 1 mins.

Question

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

https://leetcode.com/problems/linked-list-cycle-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                fast = head;
                while(slow != fast){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 718 Reading time ≈ 1 mins.

Question

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

https://leetcode.com/problems/linked-list-cycle/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 821 Reading time ≈ 1 mins.

Question

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

https://leetcode.com/problems/merge-k-sorted-lists/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    //pq,time O(nlogk), space O(K)
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        ListNode dummy = new ListNode(0);
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (int i = 0; i < lists.length; i++)
            if (lists[i] != null) pq.offer(lists[i]);//only first element will be insert to the pq
        ListNode cur = dummy;
        while(!pq.isEmpty()){
            cur.next = pq.poll();
            cur = cur.next;
            if (pq.isEmpty()) break; //last cycle dont need work
            if (cur.next != null) pq.offer(cur.next);
        }
        return dummy.next;
    }
}

Complexity:

Time complexity: O(nklogk)

Space complexity: O(k)

Posted on In ,
Symbols count in article: 588 Reading time ≈ 1 mins.

Question

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

https://leetcode.com/problems/merge-two-sorted-lists/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
           cur = cur.next;
        }
        cur.next = l1 == null ? l2: l1;
        return dummy.next;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)