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.
Solution. 递归
应该很容易想到用递归来分解计算步骤:
a. 先交换最前面两个元素
b. 再算后面的List
c. 将a/b两步结果接起来
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 not head or not head.next:
return head
_head = head.next
head.next = self.swapPairs(_head.next)
_head.next = head
return _head
网友评论