This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Can we assume this is a non-circular, singly linked list?
• Yes
• Can we assume k is a valid integer?
• Yes
• If k = 0, does this return the last element?
• Yes
• What happens if k is greater than or equal to the length of the linked list?
• Return None
• Can you use additional data structures?
• No
• Can we assume we already have a linked list class that can be used for this problem?
• Yes

## Test Cases¶

• Empty list -> None
• k is >= the length of the linked list -> None
• One element, k = 0 -> element
• General case with many elements, k < length of linked list

## Algorithm¶

• Setup two pointers, fast and slow
• Give fast a headstart, incrementing it once if k = 1, twice if k = 2, ...
• Increment both pointers until fast reaches the end
• Return the value of slow

Complexity:

• Time: O(n)
• Space: O(1)

## Code¶

In [1]:
%run ../linked_list/linked_list.py

In [2]:
class MyLinkedList(LinkedList):

def kth_to_last_elem(self, k):
return None

# Give fast a headstart, incrementing it
# once for k = 1, twice for k = 2, etc
for _ in range(k):
fast = fast.next
# If k >= num elements, return None
if fast is None:
return None

# Increment both pointers until fast reaches the end
while fast.next is not None:
fast = fast.next
slow = slow.next
return slow.data


## Unit Test¶

In [3]:
%%writefile test_kth_to_last_elem.py
import unittest

class Test(unittest.TestCase):

def test_kth_to_last_elem(self):
print('Test: Empty list')

print('Test: k >= len(list)')

print('Test: One element, k = 0')

print('Test: General case')

print('Success: test_kth_to_last_elem')

def main():
test = Test()
test.test_kth_to_last_elem()

if __name__ == '__main__':
main()

Overwriting test_kth_to_last_elem.py

In [4]:
%run -i test_kth_to_last_elem.py

Test: Empty list
Test: k >= len(list)
Test: One element, k = 0
Test: General case
Success: test_kth_to_last_elem
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.3141380250453949, "perplexity": 11589.497209158224}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-50/segments/1606141715252.96/warc/CC-MAIN-20201202175113-20201202205113-00333.warc.gz"}