Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

When you begin this problem you are given the following starter code (Java):

The block comment details the ListNode class made available to you for the solution.

Using the UMPIRE method to break the problem down:

1.  Understand

Restate the problem. Come up with (additional) test cases. Identify input/output data types, potential edge cases that may result in an error. Are there any time/space constraints?

As part of understanding the problem, I restated the problem in terms of its input, output, and the desired effect. I asked questions about what would happen when we encounter an odd-length Linked List (no swap will occur). Another consideration is if the Linked List is null or if it has a length of one. In this case, the original LinkedList should be returned.

In addition, we have the constraint that we are not allowed to modify the ListNode value variables directly, only the nodes themselves may be changed. This means we can only change what a node points to via its next variable.

2. Match

What type of problem is this? What data structure could you use? Are there general techniques you’re familiar with that could apply?

This is a Linked List problem that can be solved by using multiple pointers and a dummy head:

• The dummy head can maintain a consistent pointer to the head node even when the node the head refers to changes
• Multiple pointers can be used to point to key nodes in the linked list for swaps to occur:
  • before: the node before the pair to be swapped
  • node1: first node in the pair to swap
  • node2: second node in the pair to swap
  • after: the node after the pair to be swapped

3. Plan

Start writing pseudocode for your idea

4. Implement

Use your pseudocode to implement the idea in your chosen programming language

Python3 implementation:

5. Review

Test your code with various input to ensure you get the intended output

Here’s an example traced on a whiteboard for the input linked list:
1->2->3->4

6. Evaluate

What is the time/space complexity of your solution? Discuss how it could be improved if possible and if time permits.

Space Complexity: O(n)

Time Complexity: O(n)