Swapping Nodes in a Linked List — Find Kth from Front and Back
Advertisement
Problem 232 · Swapping Nodes in a Linked List
Difficulty: Medium · Pattern: Two Pointers for kth from end
Swap values of kth node from beginning and kth node from end.
Solutions
# Python
def swapNodes(head, k):
fast = head
for _ in range(k-1): fast = fast.next
front = fast # kth from start
slow = head
while fast.next:
slow = slow.next; fast = fast.next
# slow is now kth from end
front.val, slow.val = slow.val, front.val
return head
// Java
public ListNode swapNodes(ListNode head, int k) {
ListNode fast = head;
for (int i = 1; i < k; i++) fast = fast.next;
ListNode front = fast, slow = head;
while (fast.next != null) { fast = fast.next; slow = slow.next; }
int tmp = front.val; front.val = slow.val; slow.val = tmp;
return head;
}
// C++
ListNode* swapNodes(ListNode* head, int k) {
ListNode *fast=head, *slow=head, *front=nullptr;
for (int i=1; i<k; i++) fast=fast->next;
front=fast;
while (fast->next) { fast=fast->next; slow=slow->next; }
swap(front->val, slow->val);
return head;
}
Complexity
- Time: O(n)
- Space: O(1)
Advertisement