This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1721 (Medium): Swapping Nodes in a Linked List
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
You are given the
head
of a linked list, and an integerk
.Return the
head
of the linked list after swapping the values of thek
th node from the beginning and thek
th node from the end (the list is 1-indexed).
Examples:
Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5] Visual:
Example 2: Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5 Output: [7,9,6,6,8,7,3,0,9,5]
Example 3: Input: head = [1], k = 1 Output: [1]
Example 4: Input: head = [1,2], k = 1 Output: [2,1]
Example 5: Input: head = [1,2,3], k = 2 Output: [1,2,3]
Constraints:
- The number of nodes in the list is
n
.1 <= k <= n <= 10^5
0 <= Node.val <= 100
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
It's important to notice that the instructions don't specify that we have to actually swap the nodes, just the values. So the only thing remaining is to just find both nodes.
Since we don't know how long the linked list is, we'll have to iterate to the end of it before we can possibly find the second node to swap out. But to make things easier, we don't have to find and store the length and then calculate the difference, we can just take advantage of the fact that the distance from the kth node to the end is the same as the distance from the beginning to the kth node from the end.
We can move the first list (A) forward to the kth node, making sure to store it in a variable (nodeK), then start our staggered list (B) and iterate both until A ends, at which point we should be at the kth node from the end.
Then we just swap the values and return head.
Implementation:
The code for all four languages is almost exactly the same.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var swapNodes = function(head, k) {
let A = head, B = head, K, temp
for (let i = 1; i < k; i++) A = A.next
K = A, A = A.next
while (A) A = A.next, B = B.next
temp = K.val, K.val = B.val, B.val = temp
return head
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def swapNodes(self, head: ListNode, k: int) -> ListNode:
A, B = head, head
for i in range(1, k): A = A.next
nodeK, A = A, A.next
while A: A, B = A.next, B.next
nodeK.val, B.val = B.val, nodeK.val
return head
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode A = head, B = head, nodeK;
for (int i = 1; i < k; i++) A = A.next;
nodeK = A;
A = A.next;
while (A != null) {
A = A.next;
B = B.next;
}
int temp = nodeK.val;
nodeK.val = B.val;
B.val = temp;
return head;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode *A = head, *B = head, *nodeK;
for (int i = 1; i < k; i++) A = A->next;
nodeK = A, A = A->next;
while (A) A = A->next, B = B->next;
int temp = nodeK->val;
nodeK->val = B->val, B->val = temp;
return head;
}
};
Top comments (0)