Leetcode 24. Swap Nodes in Pairs

Question:

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Thinking

递归思考

局部交换()：
对于一个node,首先对它进行判断： 是none? 下一个元素是none?(即只有这一个元素)那么什么都不干,返回。反之，和node.next交换，node.next = 局部交换（node.next.next）,返回node.next
局部交换主要是把两个元素换个位置，把原来的儿子变成新的头结点返回。顺带帮新儿子接上了新儿子。（新儿子也是通过递归产生的新头结点）

Codes

递归版本

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        next_item = head.next
        if next_item is None:
            return head
        else:
            next_next = next_item.next
            next_item.next = head
            head.next = self.swapPairs(next_next)
            head = next_item
        return head

Performance