Swapping Adjacent Nodes in a Linked List

Introduction

In computer science, linked lists are a fundamental data structure used to store and organize a collection of elements. Each element, called a node, contains a value and a reference to the next node in the list. Today, we'll explore a common problem: swapping every two adjacent nodes in a linked list.

Problem Statement

Given a linked list, we want to swap every two adjacent nodes and return the modified list. However, there's a twist: we must solve this problem without modifying the values in the nodes. This means we can only change the connections between the nodes. Let's see how we can tackle this challenge.

To solve this problem, we'll use a technique known as node manipulation. We'll iteratively traverse the linked list, swapping pairs of adjacent nodes by adjusting their pointers. Here's a step-by-step breakdown of the solution:

1. Check if the head of the linked list exists. If not, we return null, as there's nothing to swap.

2. Create a dummy node and set its next pointer to the head of the linked list. This dummy node will serve as the new head of the modified list, simplifying the handling of edge cases.

3. Initialize three pointers: prev, curr, and next. We set prev as the dummy node, curr as the head, and next as the next node after the head.

4. Iterate through the linked list while both curr and next are not null. For each pair of adjacent nodes:
   

   • Update the next pointers of prev, curr, and next to perform the swap. We need to rearrange the connections between these three nodes.

   • Update the prev pointer to the new position after the swap, preparing it for the next pair of nodes.

   • Move curr and next two steps forward to continue the iteration.

5. Return the modified list's head, which is the dummy node's next pointer.

Implementation in JavaScript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function swapPairs(head) {
  // Check if the head exists
  if (!head || !head.next) {
    return head;
  }

  // Create a dummy node
  const dummy = new ListNode(0);
  dummy.next = head;

  let prev = dummy;
  let curr = head;
  let nextNode = head.next;

  while (curr && nextNode) {
    // Swap nodes
    prev.next = nextNode;
    curr.next = nextNode.next;
    nextNode.next = curr;

    // Update pointers
    prev = curr;
    curr = curr.next;
    nextNode = curr ? curr.next : null;
  }

  return dummy.next;
}

Testing the Implementation in JavaScript

// Helper function to create a linked list from an array of values
function createLinkedList(values) {
  if (!values.length) {
    return null;
  }
  const head = new ListNode(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new ListNode(values[i]);
    current = current.next;
  }
  return head;
}

// Helper function to convert a linked list to an array of values
function convertToArray(head) {
  const values = [];
  let current = head;
  while (current) {
    values.push(current.val);
    current = current.next;
  }
  return values;
}

// Test case
const values = [1, 2, 3, 4, 5];
const head = createLinkedList(values);
const swappedHead = swapPairs(head);
const swappedValues = convertToArray(swappedHead);

console.log("Original List: ", values);
console.log("Swapped List: ", swappedValues);

This test case creates a linked list with values [1, 2, 3, 4, 5], applies the swapPairs function to swap adjacent nodes, and then prints the original list and the swapped list for comparison.

'Original List: ' [ 1, 2, 3, 4, 5 ]
'Swapped List: ' [ 2, 1, 4, 3, 5 ]