No.24 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
-
你的算法只能使用常数的额外空间。
-
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
分析:这一题通过画图才能够比较直观的看出来思路,我们之前有提过链表的删除节点、交换节点位置等操作比列表简单方便,这里就是属于这交换类的啦。
首先初始状态是这样的,(图片来源于网络,手绘的太丑就不放出来了)
通过改变节点指针的指向确定新的连接方式 。
得到的结果如下:
之后依次后移循环上述操作,直到循环终止。
上述实现代码如下: