This content originally appeared on DEV Community and was authored by Kathan Vakharia
In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,
- Question Link ❓
- Possible Explanation ?
- Documented C++ Code ?
- Time and Space Complexity Analysis ⌛?
The Question
Given a non-empty, singly linked list with head node head, return a middle node of the linked list.
If there are two middle nodes, return the second middle node.
https://leetcode.com/problems/middle-of-the-linked-list/
? Give yourself at least 15-20 mins to figure out the solution :)
Explanation
The naive approach is very simple but it is important to understand what & why we are doing this to fully understand the optimized approach.
- Find the length of LinkedList →
L - Find the position (from start) of the node to be deleted:
floor(L/2) + 1→K- eg: for
L = 5, required node is3 = floor(5/2) + 1 - eg: for
L = 6, required node is4 = floor(6/2) + 1
- eg: for
- Reach the
Kthnode in K-1 iterations and return it.
C++ Code
Definition of Linked List
//Definition for singly-linked list.
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
Solution
ListNode *middleNode(ListNode *head)
{
ListNode *temp = head;
int count = 0;
//- finding length of LL : O(n)
while (temp)
{
count++;
temp = temp->next;
}
//pointing temp to head again
temp = head;
int nodeNo = count / 2 + 1; //doesn't matter if count is odd or even
//-Time: O(k-1)
//If I want to reach kth node, I need to go k-1 deep
for (int i = 1; i <= nodeNo - 1; i++)
{
temp = temp->next;
}
head = temp;
return head;
}
Complexity Analysis
Time Complexity: O(n)
O(n) for finding length of List + O(n/2) for reaching the required node = O(n)
Space Complexity: O(1)
We didn't use any extra space
This content originally appeared on DEV Community and was authored by Kathan Vakharia
Kathan Vakharia | Sciencx (2021-07-11T03:35:26+00:00) LinkedList Questions: Middle Element of Linked List – Naive Approach. Retrieved from https://www.scien.cx/2021/07/11/linkedlist-questions-middle-element-of-linked-list-naive-approach/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.