Linked List Popular Problems Vol. 1

Aloha guys. Today we are trying to solve three popular linked list problems: Linked List Cycle, Middle of the Linked List, and Remove Duplicates from Sorted List.

Let's start with my favorite Leetcode problem. 

Linked List Cycle

Description

Given head, the head of a linked list determines 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 denotes the index of the node that the 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.

 Example 1:

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

Example 2:

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

Example 3:

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

Solution

Let's imagine a running circle.  And then, we add two runners to this circle. 

If one of the runners is faster, it is obvious that the fastest runner will catch up with the slowest.

I'm going to use the same principle in my algorithm. I want to prepare two runners; slow and fast. After it, we should iterate till the end. Do you understand what it means 'end' in our case? We have two endings: the list has a cycle, and pointers will meet, and we have a null at the end of the list. 

Let's implement it:

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }

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

Our next today's problem is...

Middle of the Linked List

Description

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

 Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Solution

This problem can be tricky, but I will explain a few algorithms to solve it.

For example, we can iterate over the list and calculate the size of the list, and then iterate to the middle element =) Super simple. 

In the second variant, we can use the same approach as in the previous problem; two pointers. 

We are preparing slow and fast pointers and iterating till the end of the list. And that is it. When our fast pointer will be in the end, the slow one will be in the list middle.

Sure, don't forget about the borders. It is extremely important to check fast pointer is not null and fast.next, not null.

    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }

Remove Duplicates From the Sorted List

Description

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.

 Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Solution

The main trick in this problem is to understand how we can eliminate duplicate elements. Also, we should check the borders. In this algorithm, we will check the current element and the next one. If elements are the same, we should set cur.next to cur.next.next. Is it clear? you can ask me in the comments.

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