Problem Explanation

You are given the head of a linked list and an integer k. Your task is to swap the k-th node from the beginning with the k-th node from the end. The list is indexed from 1. The goal is to return the head of the modified linked list after swapping the values.

Example Walkthrough

Consider the following linked list and the value k=2:

11 -> 2 -> 3 -> 4 -> 5

The k-th node from the beginning is the node with value 2, and the k-th node from the end is the node with value 4. After swapping their values, we get:

11 -> 4 -> 3 -> 2 -> 5

So the output is [1, 4, 3, 2, 5].

Solution Approach

To solve this problem, we can follow these steps:

1. First, traverse the linked list to determine its length.
2. Calculate the positions of the nodes to be swapped - k and length - k + 1.
3. Now that we know the positions of the nodes to be swapped, traverse the list again and swap the values when the respective positions are reached. If the positions are the same, we don't need to swap anything. Return the head of the linked list.

The algorithm has a time complexity of O(n) since we traverse the linked list twice, and it uses a minimal amount of additional memory for storing the positions.

Ascii Illustration

1Initial linked list:
21 -> 2 -> 3 -> 4 -> 5
3
4Swap k = 2:
51 -> 4 -> 3 -> 2 -> 5

Python Solution

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6
7class Solution:
8    def swapNodes(self, head: ListNode, k: int) -> ListNode:
9        length, current = 0, head
10        while current:
11            length += 1
12            current = current.next
13        
14        first_pos = k
15        second_pos = length - k + 1
16        if first_pos == second_pos:
17            return head
18        
19        current, count = head, 0
20        while current:
21            count += 1
22            if count == first_pos or count == second_pos:
23                if count == first_pos:
24                    first_node, first_prev = current, prev
25                else:
26                    second_node, second_prev = current, prev
27                    first_node.val, second_node.val = second_node.val, first_node.val
28                    break
29            prev, current = current, current.next
30        
31        return head

Java Solution

1// Definition for singly-linked list.
2// public class ListNode {
3//     int val;
4//     ListNode next;
5//     ListNode() {}
6//     ListNode(int val) { this.val = val; }
7//     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
8// }
9
10class Solution {
11    public ListNode swapNodes(ListNode head, int k) {
12        int length = 0;
13        ListNode current = head;
14        
15        while (current != null) {
16            length++;
17            current = current.next;
18        }
19        
20        int firstPos = k;
21        int secondPos = length - k + 1;
22        if (firstPos == secondPos) {
23            return head;
24        }
25        
26        current = head;
27        ListNode prev = null;
28        ListNode firstNode = null, firstPrev = null;
29        ListNode secondNode = null, secondPrev = null;
30        int count = 0;
31        while (current != null) {
32            count++;
33            if (count == firstPos || count == secondPos) {
34                if (count == firstPos) {
35                    firstNode = current;
36                    firstPrev = prev;
37                } else {
38                    secondNode = current;
39                    secondPrev = prev;
40                    int temp = firstNode.val;
41                    firstNode.val = secondNode.val;
42                    secondNode.val = temp;
43                    break;
44                }
45            }
46            prev = current;
47            current = current.next;
48        }
49        
50        return head;
51    }
52}

JavaScript Solution

1// Definition for singly-linked list.
2// function ListNode(val, next) {
3//     this.val = (val===undefined ? 0 : val)
4//     this.next = (next===undefined ? null : next)
5// }
6
7/**
8 * @param {ListNode} head
9 * @param {number} k
10 * @return {ListNode}
11 */
12var swapNodes = function(head, k) {
13    let length = 0;
14    let current = head;
15    
16    while (current !== null) {
17        length++;
18        current = current.next;
19    }
20    
21    const firstPos = k;
22    const secondPos = length - k + 1;
23    if (firstPos === secondPos) {
24        return head;
25    }
26    
27    current = head;
28    let prev = null;
29    let firstNode = null, firstPrev = null;
30    let secondNode = null, secondPrev = null;
31    let count = 0;
32    while (current !== null) {
33        count++;
34        if (count === firstPos || count === secondPos) {
35            if (count === firstPos) {
36                firstNode = current;
37                firstPrev = prev;
38            } else {
39                secondNode = current;
40                secondPrev = prev;
41                let temp = firstNode.val;
42                firstNode.val = secondNode.val;
43                secondNode.val = temp;
44                break;
45            }
46        }
47        prev = current;
48        current = current.next;
49    }
50    
51    return head;
52};

C++ Solution

1// Definition for singly-linked list.
2// struct ListNode {
3//     int val;
4//     ListNode *next;
5//     ListNode() : val(0), next(nullptr) {}
6//     ListNode(int x) : val(x), next(nullptr) {}
7//     ListNode(int x, ListNode *next) : val(x), next(next) {}
8// };
9
10class Solution {
11public:
12    ListNode* swapNodes(ListNode* head, int k) {
13        int length = 0;
14        ListNode* current = head;
15        
16        while (current != nullptr) {
17            length++;
18            current = current->next;
19        }
20        
21        int firstPos = k;
22        int secondPos = length - k + 1;
23        if (firstPos == secondPos) {
24            return head;
25        }
26        
27        current = head;
28        ListNode *prev = nullptr, *firstNode = nullptr, *firstPrev = nullptr;
29        ListNode *secondNode = nullptr, *secondPrev = nullptr;
30        int count = 0;
31        while (current != nullptr) {
32            count++;
33            if (count == firstPos || count == secondPos) {
34                if (count == firstPos) {
35                    firstNode = current;
36                    firstPrev = prev;
37                } else {
38                    secondNode = current;
39                    secondPrev = prev;
40                    int temp = firstNode->val;
41                    firstNode->val = secondNode->val;
42                    secondNode->val = temp;
43                    break;
44                }
45            }
46            prev = current;
47            current = current->next;
48        }
49        
50        return head;
51    }
52};

C# Solution

1// Definition for singly-linked list.
2// public class ListNode {
3//     public int val;
4//     public ListNode next;
5//     public ListNode(int val=0, ListNode next=null) {
6//         this.val = val;
7//         this.next = next;
8//     }
9// }
10
11public class Solution {
12    public ListNode SwapNodes(ListNode head, int k) {
13        int length = 0;
14        ListNode current = head;
15        
16        while (current != null) {
17            length++;
18            current = current.next;
19        }
20        
21        int firstPos = k;
22        int secondPos = length - k + 1;
23        if (firstPos == secondPos) {
24            return head;
25        }
26        
27        current = head;
28        ListNode prev = null, firstNode = null, firstPrev = null;
29        ListNode secondNode = null, secondPrev = null;
30        int count = 0;
31        while (current != null) {
32            count++;
33            if (count == firstPos || count == secondPos) {
34                if (count == firstPos) {
35                    firstNode = current;
36                    firstPrev = prev;
37                } else {
38                    secondNode = current;
39                    secondPrev = prev;
40                    int temp = firstNode.val;
41                    firstNode.val = secondNode.val;
42                    secondNode.val = temp;
43                    break;
44                }
45            }
46            prev = current;
47            current = current.next;
48        }
49        
50        return head;
51    }
52}

Conclusion

In this article, we have provided a detailed explanation and solution to swapping the k-th node from the beginning with the k-th node from the end in a singly-linked list. The provided solutions cover Python, Java, JavaScript, C++, and C# languages and have a time complexity of O(n). Utilize these solutions to understand and master linked list problems in various programming languages.