LinkedList Questions: Middle Element of Linked List – Optimal Approach

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 Analysi…


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,

  1. Question Link ❓
  2. Possible Explanation ?
  3. Documented C++ Code ?
  4. 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

kathanvakharia

LinkedList Questions: Middle Element of Linked List - Naive Approach

Kathan Vakharia ・ Jul 11 ・ 2 min read

#algorithms #cpp #codenewbie #linkedlist

I hope you have read the previous article because I want to relate the ideas of both approaches rather than making you feel, an optimal solution is a completely new thing!

? Observation: If you recall from the last post, we can reach the middle node after floor(L/2) iterations.

Remember the above point, I'll come to this point after we see the algorithm.

Here's the algorithm.

  1. Initialize two pointers, fast and slow both pointing to head initially.

  2. Move fast double the speed than slow untill fast becomes NULL or it has reached the last node.

    //pseudo code
while fast!=NULL and fast->next != NULL
        fast = fast->next->next
        slow = slow->next

  3. return slow .

Why does this work?

First of all, we can either have an odd length linkedlist or an even length LinkedList.

  • Case 1: Odd length
    • fast will point to the last node after floor(L/2) iterations.
  • Case 2: Even Length
    • fast will become NULL after traversing the entire list in floor(L/2) iterations.

So no matter what the type of LinkedList, one of the loop termination conditions will hit after floor(L/2) iterations, and by that time slow would be pointing to the required middle node.

Image for explanation

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 *fast;
      ListNode *slow;
      fast = slow = head;

      //make fast reach the end of the list by moving it double time the slow
      while (fast != nullptr && fast->next != nullptr)
      {
          fast = fast->next->next;
          slow = slow->next;
      }
      //* now slow will point to the required node

      return slow;
  }

Complexity Analysis

N: Length of Linked List.

Time Complexity: O(N)

We are doing O(N/2) iterations which asymptotically is the same as 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


Print Share Comment Cite Upload Translate Updates
APA

Kathan Vakharia | Sciencx (2021-07-16T04:34:43+00:00) LinkedList Questions: Middle Element of Linked List – Optimal Approach. Retrieved from https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/

MLA
" » LinkedList Questions: Middle Element of Linked List – Optimal Approach." Kathan Vakharia | Sciencx - Friday July 16, 2021, https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/
HARVARD
Kathan Vakharia | Sciencx Friday July 16, 2021 » LinkedList Questions: Middle Element of Linked List – Optimal Approach., viewed ,<https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/>
VANCOUVER
Kathan Vakharia | Sciencx - » LinkedList Questions: Middle Element of Linked List – Optimal Approach. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/
CHICAGO
" » LinkedList Questions: Middle Element of Linked List – Optimal Approach." Kathan Vakharia | Sciencx - Accessed . https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/
IEEE
" » LinkedList Questions: Middle Element of Linked List – Optimal Approach." Kathan Vakharia | Sciencx [Online]. Available: https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/. [Accessed: ]
rf:citation
» LinkedList Questions: Middle Element of Linked List – Optimal Approach | Kathan Vakharia | Sciencx | https://www.scien.cx/2021/07/16/linkedlist-questions-middle-element-of-linked-list-optimal-approach/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts