Insert node into the middle of the linked listGiven a linked list containing n nodes. The problem is to insert a new node with data x at the middle of the list. If n is even, then insert the new node after the (n/2)th node, else insert the new node after the (n+1)/2th node. Show Examples: Input : list: 1->2->4->5 x = 3 Output : 1->2->3->4->5 Input : list: 5->10->4->32->16 x = 41 Output : 5->10->4->41->32->16Linked List | Set 2 (Inserting a node)We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal. C++
C
Java
Python
C#
Javascript
In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways Required knowledgeBasic C programming, Functions, Singly linked list, Dynamic memory allocation Algorithm to insert node at the middle of singly Linked ListAlgorithm to insert node at the middle of Singly Linked List
%% Input : n position to insert data in the list
Begin:
createSinglyLinkedList (head)
alloc (newNode)
If (newNode == NULL) then
write ('Unable to allocate memory.')
End if
Else then
read (data)
newNode.data ← data
temp ← head
For i ← 2 to n-1
temp ← temp.next
If (temp == NULL) then
break
End if
End for
If (temp != NULL) then
newNode.next ← temp.next
temp.next ← newNode
End if
End else
End C Exercises: Insert a new node at the middle of the Linked ListLast update on December 20 2021 09:11:05 (UTC/GMT +8 hours)Middle of the Linked ListDifficulty: Easy Understanding the ProblemProblem Description Given a non-empty, singly linked list with head node head, write a program to return a middle node of the linked list. If there are even nodes, then there would be two middle nodes, we need to print the second middle element. Example 1 Example 2 Input: 10->2->34->24->15->60 Output: 24 Explanation: As there are even number of nodes, return 24 as it is the second node among two middle elements.Solutions
Before moving forward with the question, you must understand the properties of a linked list. You can try this problem here. 1. Two-PassThe question demands to find the middle of a singly linked list. We can simply find the total length of the linked list, in this way we can identify which node falls in the middle. To find the middle node, we can traverse again until we reach (length/2)th node. Solution Steps
Pseudo Code int middleNode(ListNode head) { int l=0 ListNode p = head while (p != null) { p = p.next l = l + 1 } p = head int c = 0 while (c < l/2) { p = p.next c = c + 1 } return p.data }Complexity Analysis Time Complexity: O(n) Space Complexity: O(1) Critical Ideas To Think
2. One-PassAnother way to solve this problem is to use a little trick. Instead of traversing twice, we can create two-pointers say slow_ptr and fast_ptr.We can make the fast_ptr twice as fast as slow_ptr. So, When the fast_ptr will reach to the end of the linked list, slow_ptr would still be at the middle, thereby pointing to the mid of the linked list. Solutions Steps
Pseudo Code int middleNode(ListNode head) { ListNode slow = head ListNode fast = head while (fast != null and fast.next != null) { slow = slow.next fast = fast.next.next } return slow.data }Complexity Analysis Time Complexity: O(n) Space Complexity: O(1) Critical Ideas To Think
Comparison Of Different ApproachesSuggested Problems To Solve
Happy coding! Enjoy Algorithms. |