Linked List Popular Problems Vol. 1
This article will show how to solve three popular linked list problems: Linked List Cycle, Middle of the Linked List, and Remove Duplicates from Sorted List.
Join the DZone community and get the full member experience.
Join For FreeAloha 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;
}
Opinions expressed by DZone contributors are their own.
Comments