LeetCode 1721: Swapping Nodes in a Linked List
Problem Description
Explanation
To swap the kth node from the beginning with the kth node from the end in a linked list, we can follow these steps:
- Traverse the linked list to find the kth node from the beginning and store its value.
- Traverse the linked list again to find the kth node from the end and swap its value with the previously stored value.
- Return the modified linked list.
Time complexity: O(n) where n is the number of nodes in the linked list. Space complexity: O(1)
Solutions
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy, first = dummy, second = dummy;
// Move fast k nodes ahead
for (int i = 0; i < k; i++) {
fast = fast.next;
}
first = fast;
// Move fast to the end and slow will reach kth node from the end
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
second = slow;
// Swap values
int temp = first.val;
first.val = second.val;
second.val = temp;
return head;
}
}Loading editor...