Given a Linked List and a number K. The task is to print the value of the K-th node from the middle towards the beginning of the List. If no such element exists, then print “-1”.
Note: The position of the middle node is: (n/2)+1, where n is the total number of nodes in the list.
Examples:
Input : List is 1->2->3->4->5->6->7
K= 2
Output : 2
Input : list is 7->8->9->10->11->12
K = 3
Output : 7
Traverse the List from beginning to end and count the total number of nodes. Now, suppose 
is the total number of nodes in the List. Therefore, the middle node will be at the position (n/2)+1. Now, the task remains to print the node at (n/2 + 1 – k)th position from the head of the List.
Below is the implementation of the above idea:
C++
// CPP program to find kth node from middle// towards Head of the Linked List#include <bits/stdc++.h>using namespace std;// Linked list nodestruct Node { int data; struct Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to count number of nodesint getCount(struct Node* head){ int count = 0; // Initialize count struct Node* current = head; // Initialize current while (current != NULL) { count++; current = current->next; } return count;}// Function to get the kth node from the mid// towards begin of the linked listint printKthfrommid(struct Node* head_ref, int k){ // Get the count of total number of // nodes in the linked list int n = getCount(head_ref); int reqNode = ((n / 2 + 1) - k); // If no such node exists, return -1 if (reqNode <= 0) { return -1; } // Find node at position reqNode else { struct Node* current = head_ref; // the index of the // node we're currently // looking at int count = 1; while (current != NULL) { if (count == reqNode) return (current->data); count++; current = current->next; } }}// Driver codeint main(){ // start with empty list struct Node* head = NULL; int k = 2; // create linked list // 1->2->3->4->5->6->7 push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << printKthfrommid(head, 2); return 0;} |
Java
// Java program to find Kth node from mid// of a linked list in single traversal// Linked list nodeclass Node{ int data; Node next; Node(int d) { this.data = d; this.next = null; }}class LinkedList{ Node start; LinkedList() { start = null; } // Function to push node at head public void push(int data) { if(this.start == null) { Node temp = new Node(data); this.start = temp; } else { Node temp = new Node(data); temp.next = this.start; this.start = temp; } } //method to get the count of node public int getCount(Node start) { Node temp = start; int cnt = 0; while(temp != null) { temp = temp.next; cnt++; } return cnt; } // Function to get the kth node from the mid // towards begin of the linked list public int printKthfromid(Node start, int k) { // Get the count of total number of // nodes in the linked list int n = getCount(start); int reqNode = ((n + 1) / 2) - k; // If no such node exists, return -1 if(reqNode <= 0) return -1; else { Node current = start; int count = 1,ans = 0; while (current != null) { if (count == reqNode) { ans = current.data; break; } count++; current = current.next; } return ans; } } // Driver code public static void main(String[] args) { // create linked list // 1->2->3->4->5->6->7 LinkedList ll = new LinkedList(); ll.push(7); ll.push(6); ll.push(5); ll.push(4); ll.push(3); ll.push(2); ll.push(1); System.out.println(ll.printKthfromid(ll.start, 2)); }}// This Code is contributed by Adarsh_Verma |
Python3
# Python3 program to find kth node from # middle towards Head of the Linked List# Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data self.next = None# Function to insert a node at the # beginning of the linked list def push(head, data): if not head: # Return new node return Node(data) # allocate node new_node = Node(data) # link the old list to the new node new_node.next = head # move the head to point # to the new node head = new_node return head # Function to count number of nodesdef getCount(head): count = 0 # Initialize count current = head # Initialize current while (current ): count = count + 1 current = current.next return count# Function to get the kth node from the mid# towards begin of the linked listdef printKthfrommid(head_ref, k): # Get the count of total number of # nodes in the linked list n = getCount(head_ref) reqNode = int((n / 2 + 1) - k) # If no such node exists, return -1 if (reqNode <= 0) : return -1 # Find node at position reqNode else : current = head_ref # the index of the # node we're currently # looking at count = 1 while (current) : if (count == reqNode): return (current.data) count = count + 1 current = current.next # Driver Code if __name__=='__main__': # start with empty list head = None k = 2 # create linked list # 1.2.3.4.5.6.7 head = push(head, 7) head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) print(printKthfrommid(head, 2)) # This code is contributed by Arnab Kundu |
C#
// C# program to find Kth node from mid// of a linked list in single traversalusing System;// Linked list nodepublic class Node{ public int data; public Node next; public Node(int d) { this.data = d; this.next = null; }}public class LinkedList{ Node start; LinkedList() { start = null; } // Function to push node at head public void push(int data) { if(this.start == null) { Node temp = new Node(data); this.start = temp; } else { Node temp = new Node(data); temp.next = this.start; this.start = temp; } } //method to get the count of node public int getCount(Node start) { Node temp = start; int cnt = 0; while(temp != null) { temp = temp.next; cnt++; } return cnt; } // Function to get the kth node from the mid // towards begin of the linked list public int printKthfromid(Node start, int k) { // Get the count of total number of // nodes in the linked list int n = getCount(start); int reqNode = ((n + 1) / 2) - k; // If no such node exists, return -1 if(reqNode <= 0) return -1; else { Node current = start; int count = 1,ans = 0; while (current != null) { if (count == reqNode) { ans = current.data; break; } count++; current = current.next; } return ans; } } // Driver code public static void Main(String[] args) { // create linked list // 1->2->3->4->5->6->7 LinkedList ll = new LinkedList(); ll.push(7); ll.push(6); ll.push(5); ll.push(4); ll.push(3); ll.push(2); ll.push(1); Console.WriteLine(ll.printKthfromid(ll.start, 2)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program to find Kth node from mid// of a linked list in single traversal// Linked list nodeclass Node { constructor(val) { this.data = val; this.next = null; }} var start = null; // Function to push node at head function push(data) { if (this.start == null) { temp = new Node(data); this.start = temp; } else { temp = new Node(data); temp.next = this.start; this.start = temp; } } // method to get the count of node function getCount( start) { temp = start; var cnt = 0; while (temp != null) { temp = temp.next; cnt++; } return cnt; } // Function to get the kth node from the mid // towards begin of the linked list function printKthfromid( start , k) { // Get the count of total number of // nodes in the linked list var n = getCount(start); var reqNode = ((n + 1) / 2) - k; // If no such node exists, return -1 if (reqNode <= 0) return -1; else { current = start; var count = 1, ans = 0; while (current != null) { if (count == reqNode) { ans = current.data; break; } count++; current = current.next; } return ans; } } // Driver code // create linked list // 1->2->3->4->5->6->7 push(7); push(6); push(5); push(4); push(3); push(2); push(1); document.write(printKthfromid(start, 2));// This code is contributed by aashish1995 </script> |
Output
2
Complexity Analysis:
- Time Complexity: O(n), where n is the length of the list.
- Auxiliary Space: O(1)
Method 2 :
This method focuses on finding the K-th node from the middle towards the beginning of the List using two pointers.
Prerequisite: two pointers method in https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/
Traverse linked list using two pointers named as slow and fast. Move the fast pointer B times if it reaches the end, then no answer exists print “-1” else start moving fast and slow pointers simultaneously when the fast pointer reaches the end, the answer will the value of the slow pointer.
Below is the implementation of the above idea:
C++
// Using two pointers// CPP program to find kth node from middle// towards Head of the Linked List#include <bits/stdc++.h>using namespace std;// Linked list nodestruct Node { int data; struct Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to get the kth node from the mid// towards begin of the linked listint printKthfrommid(struct Node* head_ref, int k){ struct Node* slow = head_ref; struct Node* fast = head_ref; // initializing fast and slow pointers for( int i = 0 ; i < k ; i++ ) { if(fast && fast->next) { fast = fast->next->next; // moving the fast pointer } else { return -1; // If no such node exists, return -1 } } while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow->data;}// Driver codeint main(){ // start with empty list struct Node* head = NULL; int k = 2; // create linked list // 1->2->3->4->5->6->7 push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << printKthfrommid(head, 2); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;// Linked list nodeclass Node { int data; Node next;}class GFG { public Node head = null; /* Given a reference (pointer to pointer) to the head of * a list and an int, push a new node on the front of * the list. */ public void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head; head = new_node; } // Function to get the kth node from the mid towards // begin of the linked list public int printKthfrommid(int k) { // initializing fast and slow pointers Node slow = head; Node fast = head; for (int i = 0; i < k; i++) { if (fast != null && fast.next != null) { fast = fast.next .next; // moving the fast pointer } else { return -1; // If no such node exists, return // -1 } } while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow.data; } public static void main(String[] args) { GFG ll = new GFG(); // create linked list // 1->2->3->4->5->6->7 ll.push(7); ll.push(6); ll.push(5); ll.push(4); ll.push(3); ll.push(2); ll.push(1); int k = 2; System.out.print(ll.printKthfrommid(k)); }}// This code is contributed by lokeshmvs21. |
Python
# Python program to find kth node from middle# towards Head of the Linked List# Node classclass Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None# LinkedList classclass LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Function to get the kth node from the middle # towards begin of the linked list def printKthfrommid(self, k): slow = self.head fast = self.head for i in range(k): if (fast and fast.next): fast = fast.next.next else: return -1 while(fast and fast.next): slow = slow.next fast = fast.next.next return slow.data# Driver programllist = LinkedList()llist.push(7)llist.push(6)llist.push(5)llist.push(4)llist.push(3)llist.push(2)llist.push(1)print(llist.printKthfrommid(2))# This code is contributed by adityamaharshi21 |
C#
// C# code to implement the above approachusing System;// Linked list nodeclass Node { public int data; public Node next;}public class GFG { Node head = null; /* Given a reference (pointer to pointer) to the head of * a list and an int, push a new node on the front of * the list. */ void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head; head = new_node; } // Function to get the kth node from the mid towards // begin of the linked list int printKthfrommid(int k) { // initializing fast and slow pointers Node slow = head; Node fast = head; for (int i = 0; i < k; i++) { if (fast != null && fast.next != null) { fast = fast.next .next; // moving the fast pointer } else { return -1; // If no such node exists, return // -1 } } while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow.data; } static public void Main() { // Code GFG ll = new GFG(); // create linked list // 1->2->3->4->5->6->7 ll.push(7); ll.push(6); ll.push(5); ll.push(4); ll.push(3); ll.push(2); ll.push(1); int k = 2; Console.Write(ll.printKthfrommid(k)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Using two pointers// JS program to find kth node from middle// towards Head of the Linked List// Linked list nodeclass Node { constructor(d) { this.data = d; this.next = null; }}/* Given a reference (pointer topointer) to the head of a listand an int, push a new node onthe front of the list. */function push(head_ref, new_data) { let new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; // console.log("data",head_ref);}// Function to get the kth node from the mid// towards begin of the linked listfunction printKthfrommid(head_ref, k) { let slow = head_ref.next; let fast = head_ref.next; // initializing fast and slow pointers for (let i = 0; i < k; i++) { if (head_ref.next==null && head_ref.next==null) { head_ref.next = head_ref.next.next.next; // moving the fast pointer } else { return 2; // If no such node exists, return -1 } } while (head_ref.next==null && head_ref.next.next==null) { slow = slow.next; head_ref.next = head_ref.next.next.next; } return slow.data;}// Driver code// start with empty listlet head = new Node();let k = 2;// create linked list// 1->2->3->4->5->6->7push(head, 7);push(head, 6);push(head, 5);push(head, 4);push(head, 3);push(head, 2);push(head, 1);console.log(printKthfrommid(head, 2)); |
Output
2
Complexities Analysis:
- Time Complexity: O(n), where n is the length of the list.
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
