给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
示例: 给定 1->2->3->4, 你应该返回 2->1->4->3.
说明: 你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
思路分析: 题目要求我们使用常数的额外空间,意思是不让我们用递归。迭代就稍微麻烦一点,但思路一样,我们先看递归怎么写,然后推出迭代怎么写。
递归:
1 2 3 4 5 6 7 8
class (object) : def swapPairs (self, head) : if not head or not head.next: return head cur = head.next pre = head nex = cur.next cur.next,pre.next = pre, self.swapPairs(nex) return cur
那么迭代就很好想了,我们只需要将pre.next就指向nex.next,然后把pre,cur换成nex,nex.next即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
class (object) : def swapPairs (self, head) : if not head or not head.next: return head ret = ListNode(0 ) ret.next = head.next pre, cur = head, head.next while cur: nex = cur.next cur.next = pre if nex and nex.next: pre.next = nex.next else : pre.next = nex break pre, cur = nex, nex.next return ret.next
近期评论