In current post we discuss how to find kth node from end of the linked list that contains loop.

Finding kth node from the end of single linked list that does not contain loop is pretty much easy. Take two pointers one at the head of the list and one at k nodes from the head of the list. Traverse both the pointers simultaneously one at a time, by the time second pointer reaches end of the list, first pointer will be at kth position from the end of the list. Or if we know the length of the list in hand, traverse n-k nodes from the head of the list which gives kth node.

Following is the procedure to be followed to find kth node from the end of the linked list that contains a loop:

• From previous post we know the loop detection node, merging point node, loop length and length of the list
• If loop length >= k, we need to traverse loop length – k nodes from the merging point node
• If loop length < k, we need to traverse length of list – k nodes from the head of linked list

Consider the following list that contains loop: Dry run for the above example:

From previous posts, we know how to calculate merging point node, length of the loop and length of the list.

Consider the following figure: To find 2nd node from the end of the list:

Here loopLength (4) > k (2). To find 5th node from the end of the list:

Here loopLength (4) < k (5). Implementation for class ListNode and class SingleLinkedList is given in the previous post.

Code for the above solution is as follows:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 `package` `ds;` `public` `class` `KthNodeFromEndOfLoopedList` `{` `    ``public` `KthNodeFromEndOfLoopedList()` `    ``{` `    ``}` `    ``public` `ListNode returnLoopDetectionNode(ListNode loopedList)` `    ``{` `        ``ListNode fastNode = loopedList;` `        ``ListNode slowNode = loopedList;` `        ``while` `(fastNode.next.next != ``null``)` `        ``{` `            ``slowNode = slowNode.next;` `            ``fastNode = fastNode.next.next;` `            ``if` `(slowNode == fastNode)` `            ``{` `                ``break``;` `            ``}` `        ``}` `        ``return` `slowNode;` `    ``}` `    ``public` `int` `getLoopLength(ListNode loopDetectionNode)` `    ``{` `        ``//  Take two pointers at loop detection node and calculate loop length` `        ``ListNode P1 = loopDetectionNode;` `        ``ListNode P2 = loopDetectionNode;` `        ``int` `loopLength = ``1``;` `        ``do` `        ``{` `            ``loopLength++;` `            ``P2 = P2.next;` `        ``}` `        ``while` `(P1 != P2);` `        ``return` `(loopLength - ``1``);` `    ``}` `    ``public` `ListNode getMergingPointNode(ListNode loopedList,` `        ``ListNode loopDetectionNode)` `    ``{` `        ``ListNode P1 = loopedList;` `        ``ListNode P2 = loopDetectionNode;` `        ``while` `(P1 != P2)` `        ``{` `            ``P1 = P1.next;` `            ``P2 = P2.next;` `        ``}` `        ``return` `P1;` `    ``}` `    ``public` `int` `getMergingPointLength(ListNode loopedList,` `        ``ListNode loopDetectionNode)` `    ``{` `        ``ListNode P1 = loopedList;` `        ``ListNode P2 = loopDetectionNode;` `        ``//  Calculate length till the merging point` `        ``int` `length = ``1``;` `        ``while` `(P1 != P2)` `        ``{` `            ``P1 = P1.next;` `            ``P2 = P2.next;` `            ``length++;` `        ``}` `        ``return` `(length - ``1``);` `    ``}` `    ``public` `static` `void` `main(String[] args)` `    ``{` `        ``// Need to find kth node from end of linked list that contains loop` `        ``int` `k = ``2``;` `        ``SingleLinkedList newList = ``new` `SingleLinkedList();` `        ``newList.add(``1``);` `        ``newList.add(``2``);` `        ``ListNode loopNode = newList.add(``3``);` `        ``newList.add(``4``);` `        ``newList.add(``5``);` `        ``ListNode endNode = newList.add(``6``);` `        ``//  Creating a loop` `        ``endNode.next = loopNode;` `        ``ListNode loopedList = newList.getList();` `        ``KthNodeFromEndOfLoopedList kthNodeList = ``new` `KthNodeFromEndOfLoopedList();` `        ``ListNode loopDetectionNode = kthNodeList.returnLoopDetectionNode(loopedList);` `        ``int` `loopLength = kthNodeList.getLoopLength(loopDetectionNode);` `        ``int` `lengthTillMergingPoint = kthNodeList.getMergingPointLength(loopedList,` `                ``loopDetectionNode);` `        ``int` `lengthOfList = loopLength + lengthTillMergingPoint;` `        ``if` `(k > lengthOfList)` `        ``{` `            ``System.out.println(``"Cannot find kth in the linked list"``);` `        ``}` `        ``else` `        ``{` `            ``if` `(loopLength >= k)` `            ``{` `                ``//  Need to traverse (loopLength-k nodes from mergingPointNode to get kth Node from end of the list)` `                ``ListNode mergingPointNode = kthNodeList.getMergingPointNode(loopedList,` `                        ``loopDetectionNode);` `                ``ListNode kthNode = mergingPointNode;` `                ``for` `(``int` `i = ``0``; i < (loopLength - k); i++)` `                ``{` `                    ``if` `(kthNode != ``null``)` `                    ``{` `                        ``kthNode = kthNode.next;` `                    ``}` `                ``}` `                ``System.out.println(` `                    ``"Kth Node from end of linked list that contains loop is "` `+` `                    ``kthNode.data);` `            ``}` `            ``else` `            ``{` `                ``//  Need to traverse (lengthOfList-k nodes from head of the list to get kth Node from end of the list)` `                ``ListNode kthNode = loopedList;` `                ``for` `(``int` `i = ``0``; i < (lengthOfList - k); i++)` `                ``{` `                    ``if` `(kthNode != ``null``)` `                    ``{` `                        ``kthNode = kthNode.next;` `                    ``}` `                ``}` `                ``System.out.println(` `                    ``"Kth Node from end of linked list that contains loop is "` `+` `                    ``kthNode.data);` `            ``}` `        ``}` `    ``}` `}`

END