056.md

24. Swap Nodes in Pairs

Difficulty: 🟡 Medium

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]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Solutions

O(n) solution

Python 3

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        prev, curr, new_head = None, head, head.next

        while curr and curr.next:
            temp = curr.next
            if prev: prev.next = temp

            curr.next, temp.next = temp.next, curr
            prev, curr = curr, curr.next

        return new_head

The given solution provides an iterative approach to swap every two adjacent nodes in the linked list.

Here is a step-by-step overview of the solution:

1. Check if the given linked list is empty or contains only one node. If so, return the head as it is.
2. Initialize three pointers: prev to keep track of the previous node, curr to keep track of the current node, and new_head to store the new head of the modified list.
3. Assign the new_head as the second node in the original list (head.next).
4. Enter a loop to swap every two adjacent nodes:
   • Store the reference to the next node after curr in the variable temp.
   • If prev is not None, update prev.next to point to temp.
   • Swap the positions of curr and temp by updating the next pointers accordingly: curr.next becomes temp.next, and temp.next becomes curr.
   • Update prev to curr and curr to the next node (curr.next).
5. Return the new_head, which is the head of the modified list.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the linked list. We visit each node once and perform constant time operations.

The space complexity is O(1) because we are using a constant amount of additional space to store the pointers.

Summary

The given solution provides an iterative approach to swap every two adjacent nodes in a linked list. It maintains three pointers to keep track of the previous node, the current node, and the new head of the modified list. The solution runs in linear time and constant space complexity.

NB: If you want to get community points please suggest solutions in other languages as merge requests.