众所周知,python是业余程序员最爱的编程语言。然而仅仅会使用基本语法根本无法胜任日常的工作,数据结构和算法的知识不可或缺。而学习上述知识的一个捷径,就是练习习题。
“力扣(LeetCode)”简介
领扣网络(上海)有限公司是一家专注程序员技术提升和企业技术人才服务的科技公司。旗下品牌力扣(LeetCode)源自美国硅谷,为全球程序员提供了专业的IT技术职业化提升平台,有效帮助程序员实现快速进步和长期成长。
同时,力扣(LeetCode)也致力于解决程序员技术评估、培训、职业匹配的痛点,逐步引领互联网技术求职和招聘迈向专业化。
以上是leetcode公司的正式介绍,当然我们只要知道,leetcode的网页上有足够的算法习题就可以了。
习题简介:两两交换链表中的节点。
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
head=[1,2,3,4][2,1,3,4]head=[1,2,3][2,1,3]head=[][]
显然,这个问题超出了python初学者的学习范围。不过,我们可以试着慢慢分解问题。
首先,如果链表的输入为空集,那么输出也为空集。因此我们有如下代码块:
ifhead==None:returnhead其次,如果链表只有一个元素,我们可以直接返回它。
ifhead==None:returnheadelifhead.next==None:returnhead最后,如果链表有超过两个元素,那么我们需要将其中两个元素交换,然后再处理其余元素,这么一来,我们的题目就解答完毕了。
else:hello=head.nexthead.next=self.swapPairs(head.next.next)hello.next=headreturnhello这个算法的完整代码如下,其底层逻辑其实很简单,任何长度的链表,其除以2之后,只有两种可能,也就是余数为0,1。对于上述三种可能来说,我们均可以通过某些操作得到我们想要的答案。
classSolution(object):defswapPairs(self,head):""":typehead:ListNode:rtype:ListNode"""ifhead==None:returnheadelifhead.next==None:returnheadelse:hello=head.nexthead.next=self.swapPairs(head.next.next)hello.next=headreturnhello最后,我们来看一看结果的效率。我们可以发现,其语法虽然简单,但效率未必很高。
Superblanket