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)