But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a **free** Interview Cake problem every week.

**
You're in!
**

**
You have a linked list and want to find the kth to last node.
**

Write a function kthToLastNode that takes an integer k and the headNode of a singly-linked list, and returns the kth to last node in the list.

For example:

class LinkedListNode<Value: Equatable> {
var value: Value
var next: LinkedListNode?
init(_ value: Value) {
self.value = value
}
}
let a = LinkedListNode(1)
let b = LinkedListNode(2)
let c = LinkedListNode(3)
let d = LinkedListNode(4)
let e = LinkedListNode(5)
a.next = b
b.next = c
c.next = d
d.next = e
// returns the node with value 4 (the 2nd to last node)
var node = kthToLastNode(at: 2, forHead: a)

We can do this in time.

We can do this in space. If you're recursing, you're probably taking space on the call stack!

It might be tempting to iterate through the list until we reach the end and then walk backward k nodes.

But we have a *singly* linked list! We can’t go backward. What else can we do?

What if we had the *length* of the list?

Then we could calculate how far to walk, starting from the head, to reach the kth to last node.

If the list has n nodes:

And our target is the kth to last node:

The distance from the head to the target is n-k:

Well, we *don't* know the length of the list (n). But can we *figure it out?*

Yes, we could iterate from the head to the tail and count the nodes!

Can you implement this approach in code?

public enum KthToLastNodeError: Error, CustomStringConvertible {
case lessThanFirst(Int)
case largerThanLength(Int)
public var description: String {
switch self {
case .lessThanFirst(let k):
return "Impossible to find less than first to last node: \(k)"
case .largerThanLength(let k):
return "k is larger than the length of the linked list: \(k)"
}
}
}
func kthToLastNode(at k: Int, forHead head: LinkedListNode<Int>) throws -> LinkedListNode<Int> {
guard k >= 1 else {
throw KthToLastNodeError.lessThanFirst(k)
}
// STEP 1: get the length of the list
// start at 1, not 0
// else we'd fail to count the head node!
var listLength = 1
var currentNode = head
// traverse the whole list,
// counting all the nodes
while let nextNode = currentNode.next {
currentNode = nextNode
listLength += 1
}
// if k is greater than the length of the list, there can't
// be a kth-to-last node, so we'll return an error!
guard k <= listLength else {
throw KthToLastNodeError.largerThanLength(k)
}
// STEP 2: walk to the target node
// calculate how far to go, from the head,
// to get to the kth to last node
let howFarToGo = listLength - k
currentNode = head
for _ in 0..<howFarToGo {
if let nextNode = currentNode.next {
currentNode = nextNode
}
}
return currentNode
}

What are our time and space costs?

time and space, where n is the length of the list.

More precisely, it takes n steps to get the length of the list, and another n-k steps to reach the target node. In the worst case k=1, so we have to walk all the way from head to tail *again* to reach the target node. This is a total of 2n steps, which is .

Can we do better?

Mmmmaaaaaaybe.

The fact that we walk through our whole list once just to get the length, then walk through the list *again* to get to the kth to last element sounds like a lot of work. Perhaps we can do this in just one pass?

What if we had like a "stick" that was k nodes wide. We could start it at the beginning of the list so that the left side of the stick was on the head and the right side was on the kth node.

Then we could slide the stick down the list...

until the right side hit the end. At that point, the left side of the stick would be on the kth to last node!

How can we implement this? Maybe it'll help to keep *two* pointers?

We can allocate two variables that'll be references to the nodes at the left and right sides of the "stick"!

public enum KthToLastNodeError: Error, CustomStringConvertible {
case lessThanFirst(Int)
case largerThanLength(Int)
public var description: String {
switch self {
case .lessThanFirst(let k):
return "Impossible to find less than first to last node: \(k)"
case .largerThanLength(let k):
return "k is larger than the length of the linked list: \(k)"
}
}
}
func kthToLastNode(at k: Int, forHead head: LinkedListNode<Int>) throws -> LinkedListNode<Int> {
guard k >= 1 else {
throw KthToLastNodeError.lessThanFirst(k)
}
var leftNode = head
var rightNode = head
// Move rightNode to the kth node
for _ in 0..<(k - 1) {
// But along the way, if a rightNode doesn't have a next,
// then k is greater than the length of the list and there
// can't be a kth-to-last node! we'll raise an error
guard let rightNextNode = rightNode.next else {
throw KthToLastNodeError.largerThanLength(k)
}
rightNode = rightNextNode
}
// Starting with leftNode on the head,
// move leftNode and rightNode down the list,
// maintaining a distance of k between them,
// until rightNode hits the end of the list
while let rightNextNode = rightNode.next,
let leftNextNode = leftNode.next {
leftNode = leftNextNode
rightNode = rightNextNode
}
// Since leftNode is k nodes behind rightNode,
// leftNode is now the kth to last node!
return leftNode
}

This'll work, but **does it actually save us any time**?

We can think of this two ways.

**
First approach: use the length of the list.
**

- walk down the whole list, counting nodes, to get the total listLength.
- subtract k from the listLength to get the distance from the head node to the target node (the kth to last node).
- walk that distance from the head to arrive at the target node.

public enum KthToLastNodeError: Error, CustomStringConvertible {
case lessThanFirst(Int)
case largerThanLength(Int)
public var description: String {
switch self {
case .lessThanFirst(let k):
return "Impossible to find less than first to last node: \(k)"
case .largerThanLength(let k):
return "k is larger than the length of the linked list: \(k)"
}
}
}
func kthToLastNode(at k: Int, forHead head: LinkedListNode<Int>) throws -> LinkedListNode<Int> {
guard k >= 1 else {
throw KthToLastNodeError.lessThanFirst(k)
}
// STEP 1: get the length of the list
// start at 1, not 0
// else we'd fail to count the head node!
var listLength = 1
var currentNode = head
// traverse the whole list,
// counting all the nodes
while let nextNode = currentNode.next {
currentNode = nextNode
listLength += 1
}
// if k is greater than the length of the list, there can't
// be a kth-to-last node, so we'll return an error!
guard k <= listLength else {
throw KthToLastNodeError.largerThanLength(k)
}
// STEP 2: walk to the target node
// calculate how far to go, from the head,
// to get to the kth to last node
let howFarToGo = listLength - k
currentNode = head
for _ in 0..<howFarToGo {
if let nextNode = currentNode.next {
currentNode = nextNode
}
}
return currentNode
}

**
Second approach: maintain a k-wide "stick" in one walk down the list.
**

- Walk one pointer k nodes from the head. Call it rightNode.
- Put another pointer at the head. Call it leftNode.
- Walk both pointers, at the same speed, towards the tail. This keeps a distance of k between them.
- When rightNode hits the tail, leftNode is on the target (since it's k nodes from the end of the list).

public enum KThError: Error, CustomStringConvertible {
case lessThanFirst(Int)
case largerThanLength(Int)
public var description: String {
if case .lessThanFirst(let k) = self {
return "Impossible to find less than first to last node: \(k)"
}
if case .largerThanLength(let k) = self {
return "k is larger than the length of the linked list: \(k)"
}
return ""
}
}
func kthToLastNode(at k: Int, forHead head: LinkedListNode<Int>) throws -> LinkedListNode<Int> {
guard k >= 1 else {
throw KThError.lessThanFirst(k)
}
var leftNode = head
var rightNode = head
// Move rightNode to the kth node
for _ in 0..<(k - 1) {
// But along the way, if a rightNode doesn't have a next,
// then k is greater than the length of the list and there
// can't be a kth-to-last node! we'll raise an error
guard let rightNextNode = rightNode.next else {
throw KThError.largerThanLength(k)
}
rightNode = rightNextNode
}
// Starting with leftNode on the head,
// move leftNode and rightNode down the list,
// maintaining a distance of k between them,
// until rightNode hits the end of the list
while let rightNextNode = rightNode.next,
let leftNextNode = leftNode.next {
leftNode = leftNextNode
rightNode = rightNextNode
}
// Since leftNode is k nodes behind rightNode,
// leftNode is now the kth to last node!
return leftNode
}

In either approach, make sure to check if k is greater than the length of the linked list! That's bad input, and we'll want to raise an error.

Both approaches use time and space.

**But the second approach is fewer steps since it gets the answer "in one pass," right? Wrong.**

In the first approach, we walk one pointer from head to tail (to get the list's length), then walk another pointer from the head node to the target node (the kth to last node).

In the second approach, rightNode *also* walks all the way from head to tail, and leftNode *also* walks from the head to the target node.

So in both cases, we have two pointers taking the same steps through our list. The only difference is the *order* in which the steps are taken. The number of steps is the same either way.

**
However, the second approach might still be slightly faster, due to some caching and other optimizations that modern processors and memory have.**

Let's focus on caching. Usually when we grab some data from memory (for example, info about a linked list node), we also store that data in a small cache right on the processor. If we need to use that same data again soon after, we can quickly grab it from the cache. But if we don't use that data for a while, we're likely to replace it with other stuff we've used more recently (this is called a "least recently used" replacement policy).

Both of our algorithms access a lot of nodes in our list twice, so they *could* exploit this caching. But notice that in our second algorithm there's a much shorter time between the first and second times that we access a given node (this is sometimes called "temporal locality of reference"). Thus it seems more likely that our second algorithm will save time by using the processor's cache! But this assumes our processor's cache uses something like a "least recently used" replacement policy—it might use something else. Ultimately the *best* way to really know which algorithm is faster is to implement both and time them on a few different inputs!

Can we do better? What if we expect n to be huge and k to be pretty small? In this case, our target node will be close to the end of the list...so it seems a waste that we have to walk all the way from the beginning *twice*.

Can we trim down the number of steps in the "second trip"? One pointer will certainly have to travel all the way from head to tail in the list to get the total length...but can we store some "checkpoints" as we go so that the second pointer doesn't have to start all the way at the beginning? Can we store these "checkpoints" in constant space? Note: this approach only saves time if we know that our target node is towards the *end* of the list (in other words, n is much larger than k).

We listed two good solutions. One seemed to solve the problem in one pass, while the other took two passes. But the single-pass approach didn't take half as many steps, it just took the *same* steps in a different *order*.

So don't be fooled: "one pass" isn't always fewer steps than "two passes." Always ask yourself, "Have I actually changed the *number* of steps?"

Reset editor

Powered by qualified.io

{"id":15352768,"username":"2020-02-20_21:05:43_mqeru@","email":null,"date_joined":"2020-02-20T21:05:43.036864+00:00","first_name":"","last_name":"","full_name":"","short_name":"friend","is_anonymous":true,"is_on_last_question":false,"percent_done":0,"num_questions_done":0,"num_questions_remaining":46,"is_full_access":false,"is_student":false,"first_payment_date":null,"last_payment_date":null,"num_free_questions_left":3,"terms_has_agreed_to_latest":false,"preferred_content_language":"","preferred_editor_language":"","is_staff":false,"auth_providers_human_readable_list":"","num_auth_providers":0,"auth_email":""}

. . .