Hello geeks, in this article we are going to discuss
- What reversing a Linked List, means
- Different algorithms for Swapping Nodes in a Linked List
- The time complexity of each code
Swapping Nodes in a Linked List Leetcode Question
Swapping Nodes in a Linked List : A linked list is a linear data structure that consists of a sequence of nodes, where each node contains a value and a pointer to the next node in the sequence. Linked List has many types these are singly linked list, doubly linked list, and circular linked list.
Swapping nodes in a linked list is a common operation that can be useful in a variety of situations. For example, it can be used to reverse the order of elements in a list or to sort a list by swapping adjacent elements.
You are given the head node of a linked list and an integer k.
Return the head of the linked list after swapping the node values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).
Example 1 :
Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5]
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]
Constraints:
- The number of nodes in the list is n.
- 1 <= k <= n <= 105
- 0 <= Node.val <= 100
How To Approach?
Approach 1: Swapping the values of two nodes
One simple approach to the problem of Swapping Nodes in a Linked List is to swap their values. In other words, we can swap the values of the nodes, but keep their positions in the linked list unchanged.
Here are the steps to implement this approach:
- Find the nodes that need to be swapped, let’s call them node1 and node2.
- Swap their values.
- Update the pointers to node1 and node2 to point to the correct nodes in the list.
Java Code For This Approach:
public void swapNodes(Node node1, Node node2) {
int temp = node1.data;
node1.data = node2.data;
node2.data = temp;
}C++ Code For This Approach :
void swapNodes(Node* node1, Node* node2) {
int temp = node1->data;
node1->data = node2->data;
node2->data = temp;
}
And here is the Python code:
def swapNodes(node1, node2):
temp = node1.data
node1.data = node2.data
node2.data = tempTime complexity: O(1)
Space complexity: O(1)
Approach 2: Swapping nodes in a Linked List by changing pointers
Another approach for Swapping nodes in a Linked List is to actually swap their positions in the list. This requires changing the pointers of the nodes that come before and after the nodes are swapped.
Here are the steps to implement this approach:
- Find the nodes that need to be swapped, let’s call them node1 and node2.
- Find the nodes that come before node1 and node2, let’s call them prev1 and prev2.
- Update the pointers of prev1 and prev2 to point to the correct nodes after the swap.
- Update the pointers of node1 and node2 to point to their new neighbors.
Here is the Java code for this approach:
class Solution {
public ListNode swapNodes(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
// find the first node to be swapped
ListNode node1 = head;
for (int i = 1; i < k; i++) {
node1 = node1.next;
}
// find the second node to be swapped
ListNode node2 = head;
ListNode current = node1;
while (current.next != null) {
current = current.next;
node2 = node2.next;
}
// swap the nodes by changing the pointers
int temp = node1.val;
node1.val = node2.val;
node2.val = temp;
return head;
}
}
Here is the C++ code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode* first = nullptr;
ListNode* second = nullptr;
ListNode* cur = head;
int count = 1;
while (cur != nullptr) {
if (count == k) {
first = cur;
} else if (count == -k) {
second = head;
}
cur = cur->next;
count++;
if (second != nullptr) {
second = second->next;
}
}
if (second == nullptr) {
second = head;
for (int i = 1; i < count - k; i++) {
second = second->next;
}
}
swap(first->val, second->val);
return head;
}
};
And Here Is Python Code:
class Solution(object): def swapNodes(self, head, k): first = None second = None cur = head count = 1 while cur is not None: if count == k: first = cur elif count == -k: second = head cur = cur.next count += 1 if second is not None: second = second.next if second is None: second = head for i in range(1, count - k): second = second.next first.val, second.val = second.val, first.val return head
Time complexity: O(n)
Space complexity: O(1)
Approach 3: Swapping Nodes in a Linked List leetcode using a dummy node
This approach involves creating a new dummy node that acts as a placeholder for the nodes being swapped. Here are the steps to implement this approach:
- Create a new node called dummy, and set its next pointer to the head of the linked list.
- Find the nodes that need to be swapped, let’s call them node1 and node2.
- Find the nodes that come before node1 and node2, let’s call them prev1 and prev2. We can do this by iterating through the linked list, starting from the dummy node and stopping at the node before node1 and node2.
- Update the pointers of prev1 and prev2 to point to the correct nodes after the swap. We can do this by setting prev1’s next pointer to node2, and prev2’s next pointer to node1.
- Update the pointers of node1 and node2 to point to their new neighbors. We can do this by setting node1’s next pointer to node2’s next pointer, and node2’s next pointer to node1’s next pointer.
- Update the pointer of the dummy node to point to the new head of the linked list, which will either be node2 or node1, depending on which node was originally before the other.
Here’s the Java code:
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy, fast = dummy;
ListNode node1 = null, node2 = null;
// move the fast pointer k steps forward
for (int i = 0; i < k; i++) {
fast = fast.next;
}
// move the slow pointer to the k-th node from the beginning
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
node1 = slow;
// reset the fast pointer to the beginning
fast = dummy;
// move the fast pointer to the k-th node from the end
while (slow != null) {
node2 = fast.next;
fast = fast.next;
slow = slow.next;
}
// swap the nodes by changing the pointers
int temp = node1.val;
node1.val = node2.val;
node2.val = temp;
return dummy.next;
}
}
And here’s the Python code:
class Solution(object): def swapNodes(self, head, k): dummy = ListNode(0) dummy.next = head slow = dummy fast = dummy node1 = None node2 = None # move the fast pointer k steps forward for i in range(k): fast = fast.next # move the slow pointer to the k-th node from the beginning while fast != None: slow = slow.next fast = fast.next node1 = slow # reset the fast pointer to the beginning fast = dummy # move the fast pointer to the k-th node from the end while slow != None: node2 = fast.next fast = fast.next slow = slow.next # swap the nodes by changing the values node1.val, node2.val = node2.val, node1.val return dummy.next
Time and Space Complexity Analysis:
The time complexity of this approach is O(n), where n is the length of the linked list. This is because we need to iterate through the linked list to find the nodes that need to be swapped and then update the pointers accordingly.
The space complexity of this approach is O(1) since we only create a constant number of additional variables and do not use any extra data structures to perform the swap.
PAA (People Also Ask)
What is a linked list?
A linked list is a linear data structure that consists of a sequence of nodes, where each node contains a value and a pointer to the next node in the sequence.
What is a linked list and how is it different from a tree?
A linked list is a data structure that uses nodes to represent items and links between the nodes to indicate the order in which they should be accessed. Nodes in a linked list are typical of the same type (e.g., an item linked to another item of the same type)
so accessing an item using its linked list node address is straightforward. In contrast, a tree is a data structure that uses nodes that represent items and branches to indicate the relationship between the items. Branches may contain multiple nodes, each representing a different level of detail about an item. Accessing an item using its tree node address requires traversing the branches until you reach the node representing the item you are looking for.
Why do we need to swap nodes in a linked list?
Swapping nodes in a linked list is a common operation that can be useful in a variety of situations. For example, it can be used to reverse the order of elements in a list or to sort a list by swapping adjacent elements.
What are the different approaches to swapping nodes in a linked list?
There are several approaches to swapping nodes in a linked list, including using a temporary variable, using a recursive function, and using a dummy node.
What is the time complexity of swapping nodes in a linked list?
The time complexity of swapping nodes in a linked list depends on the approach used. Generally, the time complexity is O(n), where n is the length of the linked list.
What is the space complexity of swapping nodes in a linked list?
The space complexity of swapping nodes in a linked list also depends on the approach used. Generally, the space complexity is O(1), since only a constant amount of additional memory is needed to perform the swap. However, some approaches may require additional memory if they use recursion or create new nodes.
Can we swap two nodes in a linked list?
Yes, you can swap two nodes in a linked list. To do this, first find the node at the front of the list that you want to move, and then find the node at the back of the list that you want to move.
Then, use the following code to swap the two nodes:
node_A -> node_B
node_B -> node_A
Conclusion
Swapping nodes in a linked list is a common operation that can be useful in a variety of situations. There are several approaches to swapping nodes in a linked list, each with its own advantages and disadvantages. These approaches include using a temporary variable, using a recursive function, and using a dummy node. The time and space complexity of swapping nodes in a linked list depends on the approach used, but in general, the time complexity is O(n) and the space complexity is O(1). By understanding the different approaches to swapping nodes in a linked list, developers can choose the most appropriate approach for their specific use case.
