Swap Nodes in Pairs💰

Photo by Thomas Couillard on Unsplash

Question

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.)

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

Java Solution

Time complexity
O(n/2)
For example, if I have a list that has 7 nodes in it, then it will have 3 pairs and one extra node in total, and the loop will run only 3 times, so O(n/2)
I know we usually ignore constants in Big O, but sometimes they do matter. If I have a list of 1 million nodes as input for this question, the below code will
loop through half-million times only, so writing it as O(n) wouldn’t be correct, that’s what I think.

Code