Swap Kth Node Values - Amazon Top Interview Questions
Problem Statement :
You are given a singly linked list node and an integer k. Swap the value of the k-th (0-indexed) node from the end with the k-th node from the beginning. Constraints 1 ≤ n ≤ 100,000 where n is the number of nodes in node 0 ≤ k < n Example 1 Input node = [1, 2, 3, 4, 5, 6] k = 1 Output [1, 5, 3, 4, 2, 6] Explanation We swap 2 and 5. Example 2 Input node = [0, 6, 8, 2, 9] k = 2 Output [0, 6, 8, 2, 9] Explanation We swap 8 with 8.
Solution :
Solution in C++ :
LLNode* solve(LLNode* node, int k) {
LLNode* dummy = new LLNode(-1, node);
auto begin = node, end = node, temp = node, prevbegin = dummy, prevend = dummy;
while (k--) {
prevbegin = begin;
begin = begin->next;
temp = temp->next;
}
while (temp->next) {
prevend = end;
temp = temp->next;
end = end->next;
}
prevbegin->next = end;
prevend->next = begin;
auto bnex = begin->next;
begin->next = end->next;
end->next = bnex;
return dummy->next;
}
Solution in Python :
class Solution:
def solve(self, node, k):
prev = node
curr = node
first = node
while curr.next != None:
curr = curr.next
if k > 0:
first = first.next
if k <= 0:
prev = prev.next
k -= 1
first.val, prev.val = prev.val, first.val
return node
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →