Table of contents

Swap nodes in a Linked List

Given a singly linked list, the task is to swap every two adjacent nodes and return the modified list. If the number of nodes is odd, the last node should remain the same.

Input-Output Examples

Example 1:

  • Input: 1 -> 2 -> 3 -> 4 -> NULL
  • Output: 2 -> 1 -> 4 -> 3 -> NULL

Example 2:

  • Input: 1 -> 2 -> 3 -> NULL
  • Output: 2 -> 1 -> 3 -> NULL

Example 3:

  • Input: 1 -> NULL
  • Output: 1 -> NULL

Approach:
Technique to be used: Iterative approach with pointer manipulation

To swap nodes in pairs, we can use an iterative approach to rearrange the pointers of the nodes in the linked list. We will maintain a dummy node to simplify the handling of the head of the list.

Steps to implement:

  1. Initialize a dummy node and set its next pointer to the head of the list.
  2. Initialize a pointer current to the dummy node.
  3. Traverse the list and swap nodes in pairs:
    • Set first and second pointers to the two nodes to be swapped.
    • Adjust the pointers to swap the nodes.
    • Move the current pointer to the next pair.
  4. Return the modified list starting from the node next to the dummy node.

C++ Program to swap nodes in a linked list

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* current = &dummy;

        while (current->next != NULL && current->next->next != NULL) {
            ListNode* first = current->next;
            ListNode* second = current->next->next;

            first->next = second->next;
            second->next = first;
            current->next = second;

            current = first;
        }

        return dummy.next;
    }
};

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    Solution sol;
    ListNode* result = sol.swapPairs(head);

    // Printing the modified linked list
    cout << "Modified list: ";
    printList(result);

    return 0;
}

Java program to swap nodes in a linked list

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;

        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;

            first.next = second.next;
            second.next = first;
            current.next = second;

            current = first;
        }

        return dummy.next;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> 4 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        Solution sol = new Solution();
        ListNode result = sol.swapPairs(head);

        // Printing the modified linked list
        System.out.print("Modified list: ");
        printList(result);
    }
}

Python Program to swap nodes in a linked list

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        current = dummy
        
        while current.next and current.next.next:
            first = current.next
            second = current.next.next
            
            first.next = second.next
            second.next = first
            current.next = second
            
            current = first
        
        return dummy.next

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> 4 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

sol = Solution()
result = sol.swapPairs(head)

# Printing the modified linked list
print("Modified list:", end=" ")
print_list(result)

DSA

Related Articles