R@M3$H.NBlog

[Linked List] Find kth Node from the end of Linked List that contains Loop

17 September, 2013 - 5 min read

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 &gt; lengthOfList)
        {
            System.out.println("Cannot find kth in the linked list");
        }
        else
        {
            if (loopLength &gt;= 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