Reverse the First k Nodes

Given the head of a singly linked list and an integer k, reverse the order of the first k nodes and leave the rest of the list as it is. If k is greater than or equal to the length, reverse the whole list. If k <= 1, return the list unchanged.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5

Input:  head = 1 -> 2 -> 3, k = 5
Output: 3 -> 2 -> 1

Constraints

• 0 <= number of nodes <= 10**4
• 0 <= k <= 10**4
• Target: O(k) time, O(1) extra space

Goals

• Reverse a prefix of a list iteratively
• Reconnect the reversed prefix to the untouched remainder