Kth Node From End of Linked List
Description
Given the head of a singly linked list and an integer k, return the value of the kth node from the end of the list.
The 1st node from the end is the last node, the 2nd node from the end is the second-to-last node, and so on.
Example 1:
Input: head = [1, 2, 3, 4, 5], k = 2
Output: 4
Explanation: The linked list is 1 -> 2 -> 3 -> 4 -> 5. Counting from the end:
- 1st from end: 5
- 2nd from end: 4
So the 2nd node from the end has value 4.
Example 2:
Input: head = [1, 2, 3, 4, 5], k = 1
Output: 5
Explanation: The 1st node from the end is the last node, which has value 5.
Example 3:
Input: head = [1, 2, 3, 4, 5], k = 5
Output: 1
Explanation: The 5th node from the end is the first node (head), which has value 1.
Constraints
The number of nodes in the list is n1 <= k <= n <= 1001 <= Node.val <= 100
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Two pointers
- Approach
- Move the first pointer k steps ahead, then move both pointers together. When the first pointer reaches the end, the second pointer is at the kth node from the end.
- Complexity
- One pass with O(1) space using two pointers
Solutions
Show PY Solution
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def solution(head: ListNode, k: int) -> int:
slow = fast = head
for _ in range(k):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
return slow.val
# o(1) but not elegant
# n = head
# length = 0
# while n:
# length += 1
# n = n.next
#
# i = -1
# n = head
# while n:
# i += 1
# if i == (length - k):
# return n.val
# n = n.next
#
# return -1
# array (o(n) space)
# n = head
# arr = []
# while n:
# arr.append(n.val)
# n = n.next
#
# return arr[-k]