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 LL
8  Second Argument : A positive integer k
9
10Output: 
11  Kth Node from the end of the given list.

1Example 1 :
2  Input : 
3    LL = 1 -> 2 -> 3 -> 4 -> 5
4    k = 2
5
6  Output: Node with data 3
7
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 -> 10
5    k = 13
6
7  Output: null
8
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.

Solution Approaches

By Finding Number of Nodes

Prerequisite

• LinkedList Data Structure

Algorithm

1Input : Head of the linked list is given
2
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 null
13
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 class
4    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 list
14    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 list
20        while(current != null) {
21            current = current.next;
22            n++;
23        }
24
25        // assign current to head of the list
26        current = head;
27
28        // kth node from end means (n-k)th node from start
29        int counter = n-k;
30        while (counter != 0) {
31            // k is greater than size (n) of the linked list
32            // current pointer reaches null
33            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 values
43    private ListNode constructList(int[] array) {
44        // create dummy head node, this helps to avoid null checks
45        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 list
54        return head.next;
55    }
56
57    // Helper method to print given linked list
58    private void print(ListNode head) {
59        StringBuilder sb = new StringBuilder();
60
61        while(head != null) {
62            sb.append(head.data +" -> ");
63            head = head.next;
64        }
65        sb.append("NULL");
66        System.out.println(sb.toString());
67    }
68
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

Prerequisite

• LinkedList Data Structure
• Two Pointer Technique

Algorithm

1Input : Head of the linked list and k
2
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 list
7        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

1public class LinkedListKthNodeFromListEnd {
2
3    // ListNode class
4    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 list
14    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 list
20        while(current != null) {
21            current = current.next;
22            n++;
23        }
24
25        // assign current to head of the list
26        current = head;
27
28        // kth node from end means (n-k)th node from start
29        int counter = n-k;
30        while (counter != 0) {
31            // k is greater than size (n) of the linked list
32            // current pointer reaches null
33            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 values
43    private ListNode constructList(int[] array) {
44        // create dummy head node, this helps to avoid null checks
45        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 list
54        return head.next;
55    }
56
57    // Helper method to print given linked list
58    private void print(ListNode head) {
59        StringBuilder sb = new StringBuilder();
60
61        while(head != null) {
62            sb.append(head.data +" -> ");
63            head = head.next;
64        }
65        sb.append("NULL");
66        System.out.println(sb.toString());
67    }
68
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