I am working on the last 2-hour block of the day. My wife was trying to make a payment for our Internet service, but she needs a number that can only be found in a previous bill receipt. Apparently she can not find one, so at the end of the workday we will go to make a payment in person and will hopefully keep the receipt, so this situation does not repeat.
I worked on the LeetCode 876 Middle of the Linked List problem. If interested please check the LeetCode web site to make sure the requirements are up to date.
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. Constraints: The number of nodes in the list is in the range [1, 100]. o 1 <= Node.val <= 100 Related Topics: o Linked List o Two Pointers
We are given a singly linked list and need to return the middle node. We will have to traverse the linked list twice or with two pointers. Another approach would be to store the nodes and after traversing the linked list, determine the midpoint and return the associated node.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
}
}
The signature of the function of interest takes the linked list and returns the midpoint node that needs to be found by it.
Since we need to understand and operate on the linked list, we are given the description of the ListNode class which is used to build the linked list.
We will be solving this problem in Java using the VSCode IDE on a Windows platform. Since we are taking such an approach and not using the on-line IDE provided by LeetCode, we will have to develop a test scaffold. The test code will read the input line, populate the linked list, call the function of interest, and display the output. Please note that the test scaffold IS NOT PART OF THE SOLUTION.
1,2,3,4,5 main <<< arr: [1, 2, 3, 4, 5] main <<< head: 1 -> 2 -> 3 -> 4 -> 5 main <<< output: 3 -> 4 -> 5 main <<< output: 3 -> 4 -> 5 1,2,3,4,5,6 main <<< arr: [1, 2, 3, 4, 5, 6] main <<< head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 main <<< output: 4 -> 5 -> 6 main <<< output: 4 -> 5 -> 6 1 main <<< arr: [1] main <<< head: 1 main <<< output: 1 main <<< output: 1 1,2 main <<< arr: [1, 2] main <<< head: 1 -> 2 main <<< output: 2 main <<< output: 2 1,2,3 main <<< arr: [1, 2, 3] main <<< head: 1 -> 2 -> 3 main <<< output: 2 -> 3 main <<< output: 2 -> 3
We are provided a list of integers in the input line. We need to read the line. We could then loop on the input line while allocating nodes for the linked list, or we could populate an int[] array and then use the array to populate the linked list. We will use the second approach.
After populating the array, our test code displays the contents of the array to make sure all is well so far.
It appears that the next step is to populate the linked list. The linked list is then displayed. This is done to verify that the linked list is correct.
We then appear to make calls to two implementations of the function of interest. After each call the output which is the linked list starting at the midpoint, is displayed. Both implementations seem to be returning the proper result.
Note that the midpoint element should be tested against linked lists with even and odd numbers of nodes.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read list node values into int[] ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** populate the linked list ****
ListNode head = null;
for (int i = arr.length - 1; i >= 0; i--) {
if (head == null)
head = new ListNode(arr[i]);
else
head = new ListNode(arr[i], head);
}
// ???? ????
System.out.print("main <<< head: ");
head.printList();
// **** call the function of interest ****
ListNode mid = middleNode0(head);
// **** display the middle node ****
System.out.print("main <<< output: ");
mid.printList();
// **** call the function of interest ****
mid = middleNode(head);
// **** display the middle node ****
System.out.print("main <<< output: ");
mid.printList();
}
Our test scaffold reads the input line and populates the int[] `arr`. With the contents of the int[] `arr` the linked list is created and populated. We then display the contents of the linked list to verify that all is well before we make a call to the implementations of the function of interest.
/**
* Definition for singly-linked list.
*/
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
void printList() {
ListNode node = this;
while (node != null) {
System.out.print(node.val);
if (node.next != null)
System.out.print(" -> ");
else
System.out.println();
node = node.next;
}
}
}
Since we are solving the problem in our machine and not using the on-line IDE provided by LeetCode, we need to implement the ListNode class. Note that the method `printList()` has been added to the class. We will use it to display the contents of the linked lists. Please note that this method IS NOT PART OF THE SOLUTION.
/**
* Given the head of a singly linked list,
* return the middle node of the linked list.
*
* Using a stack.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 36.2 MB, less than 89.35% of Java online submissions.
*
* Runtime O(n) - Space: O(n)
*/
static public ListNode middleNode0(ListNode head) {
// **** initialization ****
Stack<ListNode> stack = new Stack<>();
// **** traverse the linked list - O(n) ****
while (head != null) {
stack.push(head);
head = head.next;
}
// **** return middle node ****
return stack.elementAt(stack.size() / 2);
}
In this implementation of the function of interest we start by declaring a stack of type Integer.
We then enter a while loop which is used to traverse the linked list. We could have used a for loop instead.
After the linked list has been traversed, we return the midpoint element in the stack by performing simple arithmetic.
The comments section of this implementation shows the runtime information for this code.
/**
* Given the head of a singly linked list,
* return the middle node of the linked list.
*
* Using two pointers.
*
* 36 / 36 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 36.7 MB
*
* Runtime : O(n) - Space: O(1)
*/
static public ListNode middleNode(ListNode head) {
// **** initialization ****
ListNode p = head;
ListNode q = head;
// **** traverse the list - O(n) ****
while (p != null && p.next != null) {
p = p.next.next;
q = q.next;
}
// **** return middle node ****
return q;
}
This is a second implementation of the function of interest. This one does not make use of additional space.
We3 start by initializing two pointers. Pointer `p` moves forward two nodes at a time, while pointer `q` does so moving only one node at a time.
When we exit the loop we return the `q` pointer which should be pointing to the midpoint in the linked list.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John