![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
k’th Node from End of Linked List
Problem Statement
1Problem Description :2Given a linked list LL and a positive integer k, find the kth node from the end of the list.34Note: If k is greater than the size of the list, return null.56Input:7 First Argument : head of the linked list LL8 Second Argument : A positive integer k910Output:11 Kth Node from the end of the given list.
1Example 1 :2 Input :3 LL = 1 -> 2 -> 3 -> 4 -> 54 k = 256 Output: Node with data 378 Explanation :9 As per input, the 2nd node from the end of the linked list is 4.
1Example 2 :23 Input :4 LL = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 105 k = 1367 Output: null89 Explanation :10 Given Linked List has 10 nodes and we are trying to find the 13th node from the end of the list, which does not exist. So output is null.
Solution Approaches
By Finding Number of Nodes
Prerequisite
Algorithm
1Input : Head of the linked list is given23Step 0: Initialize slow and fast pointer at head of the node.45Step 1: Traverse Linked List to find number of nodes (n) of the linked list.67Step 2: Traverse Linked List to n-k times to get the middle element.89Step 1 in Detail :10Step A : Initialize n to 0 and initialize current node at the head of the linked list.11Step B : Increment n and move current pointer by one node ahead.12Step C : Repeat Step B until current becomes null1314Step 2 in Detail :15Step A : Initialize current node at the head of the linked list.16Step B : Move the current node one step ahead n-k times.17Step C : Return current node (middle element of the linked list)
Code Implementation
1public class LinkedListKthNodeFromListEnd {23 // ListNode class4 class ListNode {5 ListNode next;6 int data;78 ListNode(int data) {9 this.data = data ;10 }11 }1213 // Method to find k'th node from end of linked list14 public ListNode getKthNodeFromLast(ListNode head, int k){1516 ListNode current = head;17 int n = 0;1819 // Traverse over list and find size of the linked list20 while(current != null) {21 current = current.next;22 n++;23 }2425 // assign current to head of the list26 current = head;2728 // kth node from end means (n-k)th node from start29 int counter = n-k;30 while (counter != 0) {31 // k is greater than size (n) of the linked list32 // current pointer reaches null33 if(current == null){34 return null;35 }36 current = current.next;37 counter--;38 }39 return current;40 }4142 // Helper method to construct a linkedList by giving array of values43 private ListNode constructList(int[] array) {44 // create dummy head node, this helps to avoid null checks45 ListNode head = new ListNode(-1);46 ListNode current = head;4748 for(int i=0 ; i<array.length; i++){49 current.next = new ListNode(array[i]);50 current = current.next;51 }52 // as head node pointed to some dummy node ,53 // head.next is our actual head of the linked list54 return head.next;55 }5657 // Helper method to print given linked list58 private void print(ListNode head) {59 StringBuilder sb = new StringBuilder();6061 while(head != null) {62 sb.append(head.data +" -> ");63 head = head.next;64 }65 sb.append("NULL");66 System.out.println(sb.toString());67 }6869 public static void main(String[] args){70 LinkedListKthNodeFromListEnd obj = new LinkedListKthNodeFromListEnd();71 int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};7273 ListNode head = obj.constructList(array);74 int k = 13;75 ListNode resultNode = obj.getKthNodeFromLast(head, k);76 System.out.println(resultNode.data);77 }7879}
Complexity Analysis
- Time Complexity : O(n) where n is the length of the linked list
- Space Complexity : O(1)
Using Two Pointer Technique
Prerequisite
Algorithm
1Input : Head of the linked list and k23Step 0: Initialize slow and fast pointer at head node of the linked list.45Step 1: Move forward fast pointer k times.6 // case where k is greater than length of the linked list7 if fast reaches end of the list (null) before k times return null89Step 2: Now move both slow and fast pointers one node ahead.10 It means slow and fast pointers maintain distance of k nodes.1112Step 3: Repeat Step2 until fast reaches the end of the linked list.1314Step 4: return slow pointer, fast reaches end of the list means,15 slow will be k nodes far from end, which is our target.1617Output : k'th node from end of the linked list.
Example Dry Run
Input : head node of the linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 2
Step 2:
Move both slow and fast pointers one node ahead until fast reaches null (or end of the linked list)
Output : 4
Code Implementation
- Java
- Python
1public class LinkedListKthNodeFromListEnd {23 // ListNode class4 class ListNode {5 ListNode next;6 int data;78 ListNode(int data) {9 this.data = data ;10 }11 }1213 // Method to find k'th node from end of linked list14 public ListNode getKthNodeFromLast(ListNode head, int k){1516 ListNode current = head;17 int n = 0;1819 // Traverse over list and find size of the linked list20 while(current != null) {21 current = current.next;22 n++;23 }2425 // assign current to head of the list26 current = head;2728 // kth node from end means (n-k)th node from start29 int counter = n-k;30 while (counter != 0) {31 // k is greater than size (n) of the linked list32 // current pointer reaches null33 if(current == null){34 return null;35 }36 current = current.next;37 counter--;38 }39 return current;40 }4142 // Helper method to construct a linkedList by giving array of values43 private ListNode constructList(int[] array) {44 // create dummy head node, this helps to avoid null checks45 ListNode head = new ListNode(-1);46 ListNode current = head;4748 for(int i=0 ; i<array.length; i++){49 current.next = new ListNode(array[i]);50 current = current.next;51 }52 // as head node pointed to some dummy node ,53 // head.next is our actual head of the linked list54 return head.next;55 }5657 // Helper method to print given linked list58 private void print(ListNode head) {59 StringBuilder sb = new StringBuilder();6061 while(head != null) {62 sb.append(head.data +" -> ");63 head = head.next;64 }65 sb.append("NULL");66 System.out.println(sb.toString());67 }6869 public static void main(String[] args){70 LinkedListKthNodeFromListEnd obj = new LinkedListKthNodeFromListEnd();71 int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};7273 ListNode head = obj.constructList(array);74 int k = 13;75 ListNode resultNode = obj.getKthNodeFromLast(head, k);76 System.out.println(resultNode.data);77 }7879}
Complexity Analysis
- Time Complexity : O(n) where n is the length of the linked list
- Space Complexity : O(1)
Comparison of Approaches
Approach | Time Complexity | Space Complexity | Remarks |
---|---|---|---|
By Finding Length of the Linked List | O(n) | O(1) | Two Traversals |
Using Two Pointer Technique | O(n) | O(1) | Single Traversal |