 Tagged
• DSA Problems
• Two Pointer Technique
•

# Problem Statement

```1Problem Description : 2Given a linked list LL and a positive integer k, find the kth node from the end of the list.3
4Note: If k is greater than the size of the list, return null.5
6Input: 7  First Argument : head of the linked list LL8  Second Argument : A positive integer k9
10Output: 11  Kth Node from the end of the given list.```

```1Example 1 :2  Input : 3    LL = 1 -> 2 -> 3 -> 4 -> 54    k = 25
6  Output: Node with data 37
8  Explanation : 9  As per input, the 2nd node from the end of the linked list is 4.```

```1Example 2 :2  3  Input : 4    LL = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 105    k = 136
7  Output: null8
9  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.```

# By Finding Number of Nodes

## Algorithm

```1Input : Head of the linked list is given2
3Step 0: Initialize slow and fast pointer at head of the node.4
5Step 1: Traverse Linked List to find number of nodes (n) of the linked list.6
7Step 2: Traverse Linked List to n-k times to get the middle element.8
9Step 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 null13
14Step 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 {2
3    // ListNode class4    class ListNode {5        ListNode next;6        int data;7
8        ListNode(int data) {9            this.data = data ;10        }11    }12
13    // Method to find k'th node from end of linked list14    public ListNode getKthNodeFromLast(ListNode head, int k){15
16        ListNode current = head;17        int n = 0;18
19        // Traverse over list and find size of the linked list20        while(current != null) {21            current = current.next;22            n++;23        }24
25        // assign current to head of the list26        current = head;27
28        // 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    }41
42    // 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;47
48        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    }56
57    // Helper method to print given linked list58    private void print(ListNode head) {59        StringBuilder sb = new StringBuilder();60
69    public static void main(String[] args){70        LinkedListKthNodeFromListEnd obj = new LinkedListKthNodeFromListEnd();71        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};72
73        ListNode head = obj.constructList(array);74        int k = 13;75        ListNode resultNode = obj.getKthNodeFromLast(head, k);76        System.out.println(resultNode.data);77    }78
79}```

## Complexity Analysis

• Time Complexity : O(n) where n is the length of the linked list
• Space Complexity : O(1)

# Using Two Pointer Technique

## Algorithm

```1Input : Head of the linked list and k2
3Step 0: Initialize slow and fast pointer at head node of the linked list.4
5Step 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 null 8        9Step 2: Now move both slow and fast pointers one node ahead. 10        It means slow and fast pointers maintain distance of k nodes.11
12Step 3: Repeat Step2 until fast reaches the end of the linked list. 13
14Step 4: return slow pointer, fast reaches end of the list means, 15        slow will be k nodes far from end, which is our target.16
17Output : 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

• Initialization : Initialize slow and fast pointer to head node of the linked list

• Step 1 : Move fast pointer k times

• Step 2:

Move both slow and fast pointers one node ahead until fast reaches null (or end of the linked list)

• Iteration 1: slow at 2 and fast at 4 (maintaining distance of 2 which is k)

• Iteration 2: slow at 3 and fast at 5

• Iteration 3: slow at 4 and fast at null (reached end of the linked list)

Output : 4

## Code Implementation

1. Java
2. Python

```1public class LinkedListKthNodeFromListEnd {2
3    // ListNode class4    class ListNode {5        ListNode next;6        int data;7
8        ListNode(int data) {9            this.data = data ;10        }11    }12
13    // Method to find k'th node from end of linked list14    public ListNode getKthNodeFromLast(ListNode head, int k){15
16        ListNode current = head;17        int n = 0;18
19        // Traverse over list and find size of the linked list20        while(current != null) {21            current = current.next;22            n++;23        }24
25        // assign current to head of the list26        current = head;27
28        // 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    }41
42    // 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;47
48        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    }56
57    // Helper method to print given linked list58    private void print(ListNode head) {59        StringBuilder sb = new StringBuilder();60
69    public static void main(String[] args){70        LinkedListKthNodeFromListEnd obj = new LinkedListKthNodeFromListEnd();71        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};72
73        ListNode head = obj.constructList(array);74        int k = 13;75        ListNode resultNode = obj.getKthNodeFromLast(head, k);76        System.out.println(resultNode.data);77    }78
79}```

## Complexity Analysis

• Time Complexity : O(n) where n is the length of the linked list
• Space Complexity : O(1)

# Comparison of Approaches

ApproachTime ComplexitySpace ComplexityRemarks
By Finding Length of the Linked ListO(n)O(1)Two Traversals
Using Two Pointer TechniqueO(n)O(1)Single Traversal

• DSA Problems