Approach #1 (One pass algorithm) [Accepted]
One thing we know we will need right off the bat is a way to swap two neighboring nodes in a list. The other thing that is immediately obvious is that we are going to have to walk over the nodes in the list and swap them as we make this traversal. Now, we just need to hammer out the details (see the algorithm below).
For the purposes of the algorithm, assume we have a function called swap that will take a node and swap it with its next and return a pointer to that next node with the two nodes now swapped (see swap's implementation in the Python code below).
- Call swap on the current head of the list and save the result as the new head (this head will be what we return at the end of the problem). So, in the input given in the problem statement, head would be equal to the node with the value 2 and have a pointer to the node with the value 1.
- Declare a variable curr that points to the next of the next of head (
curr = head.next.next).
- We will also declare a variable called prev that will help us link up swapped nodes. Its use will become more more obvious later.
- Start a while loop that updates by setting
curr = curr.next.nextat the end of each iteration. The loop will end when curr either is null (indicating there are no more pairs to swap) or curr's next is null indicating the list had an odd number of nodes and in which case the last node can just be left as is. Inside the loop:
- Set curr equal to the result of swapping the 2 nodes. In the case of the input given in the problem statement, our list would now look like this (remember we had already swapped the first 2 nodes):
2->1->3 4->3->null # essentially, 2 lists
- This is not yet correct because we want 1 to point to 4. So, we use prev (which currently would be equal to the node with value 1) and set it to point to the 4 node:
- We must update the prev to point to the second node from the swapped nodes.
- And now of course we move on to the next node that hasn't already been involved in a swap:
curr = curr.next.next
- Return the head node.
class Solution(object): def swapPairs(self, head): """ :type head: ListNode :rtype: ListNode """ if head == None: return None if head.next == None: return head def swap(f): s = f.next t = s.next s.next = f f.next = t return s head = swap(head) prev = head.next curr = head.next.next while (curr != None) and (curr.next != None): curr = swap(curr) prev.next = curr prev = curr.next curr = curr.next.next return head
- Time complexity : O(n).
We make at most a single pass over every item in the list performing constant time operations, thus the complexity linearly in with the size on the input list and is O(n).
- Space complexity : O(1). We only used constant extra space.