Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given <code>1->2->3->4</code>, you should return the list as <code>2->1->4->3</code>.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
这道题不算难,是基本的链表操作题,我们可以分别用递归和迭代来实现。对于迭代实现,还是需要建立dummy节点,注意在连接节点的时候,最好画个图,以免把自己搞晕了,参见代码如下:
解法一:
递归的写法就更简洁了,实际上利用了回溯的思想,递归遍历到链表末尾,然后先交换末尾两个,然后依次往前交换:
解法二: