Description:
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Examples:
Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]Solution in Python:
To solve the problem of swapping every two adjacent nodes in a linked list, we need to manipulate the pointers of the nodes rather than just their values.
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# Create a dummy node that acts as the new head of the modified list
dummy = ListNode(0)
dummy.next = head
current = dummy
# Traverse the list in pairs
while current.next and current.next.next:
# Identify the nodes to be swapped
first = current.next
second = current.next.next
# Swapping the nodes
first.next = second.next
second.next = first
current.next = second
# Move the pointer two nodes ahead
current = first
# Return the new head of the list
return dummy.next
Detailed Comments:
- Dummy Node Initialization:
- We create a dummy node (
dummy = ListNode(0)) which points to the head of the list. This helps in handling edge cases where the list length is less than 2 and simplifies the pointer manipulations. dummy.next = headensures the dummy node is linked to the head of the input list.- We use a
currentpointer initialized to the dummy node (current = dummy) to keep track of the node before the pair we’re currently processing.
- We create a dummy node (
- Traversal and Swapping:
- We traverse the list in pairs using the condition
while current.next and current.next.nextto ensure there are at least two nodes to swap. first = current.nextandsecond = current.next.nextare used to identify the two nodes that need to be swapped.- The swapping is done in three steps:
first.next = second.nextchanges the next pointer of the first node to point to the node after the second node.second.next = firstchanges the next pointer of the second node to point to the first node.current.next = secondchanges the next pointer of the node before the pair to point to the second node, effectively completing the swap.
- After swapping, we move the
currentpointer two nodes ahead (current = first) to continue the process with the next pair of nodes.
- We traverse the list in pairs using the condition
- Return New Head:
- After processing all pairs, the new head of the list is given by
dummy.next.
- After processing all pairs, the new head of the list is given by
This approach ensures that we only change the pointers of the nodes and not their values, which is required by the problem constraints. The time complexity of this solution is O(N), where N is the number of nodes in the linked list, as we only traverse the list once.
Solution in Javascript:
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val);
* this.next = (next===undefined ? null : next);
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
// Create a dummy node that acts as the new head of the modified list
let dummy = new ListNode(0);
dummy.next = head;
let current = dummy;
// Traverse the list in pairs
while (current.next !== null && current.next.next !== null) {
// Identify the nodes to be swapped
let first = current.next;
let second = current.next.next;
// Swapping the nodes
first.next = second.next;
second.next = first;
current.next = second;
// Move the pointer two nodes ahead
current = first;
}
// Return the new head of the list
return dummy.next;
};Solution in Java:
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// Create a dummy node that acts as the new head of the modified list
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
// Traverse the list in pairs
while (current.next != null && current.next.next != null) {
// Identify the nodes to be swapped
ListNode first = current.next;
ListNode second = current.next.next;
// Swapping the nodes
first.next = second.next;
second.next = first;
current.next = second;
// Move the pointer two nodes ahead
current = first;
}
// Return the new head of the list
return dummy.next;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode SwapPairs(ListNode head) {
// Create a dummy node that acts as the new head of the modified list
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
// Traverse the list in pairs
while (current.next != null && current.next.next != null) {
// Identify the nodes to be swapped
ListNode first = current.next;
ListNode second = current.next.next;
// Swapping the nodes
first.next = second.next;
second.next = first;
current.next = second;
// Move the pointer two nodes ahead
current = first;
}
// Return the new head of the list
return dummy.next;
}
}