Solution: Swapping Nodes in a Linked List

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 integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth 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;
    }
};