前言
上一篇文章给自己立了一个大大的flag。自己立的flag，跪着也要完成。
有时候会想，算法题这么难，为啥要折磨自己呢？我觉得在做算法题的过程中，
- 能解决眼高手低的问题，心里想的是一套，真正实践起来可能有这样那样的问题。聪明的古人有诗为证
纸上得来终觉浅，绝知此事要躬行
- 锻炼了编码的严谨性。为了看到大大的Accepted，必须要考虑到各种可能性。
- 前面说的都很虚，最终还是为了面试的时候，能胸有成竹点，不被刷掉。（想起了Homebrew作者 Max Howell 大神在面试Google的时候，因为不会在白板上翻转二叉树被拒了，连这种级别的大神也会因为算法题被拒，只能说Google太死板了，可能大公司就是这样吧）
话不多说，开始今天的解题。
题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例
给定 1->2->3->4, 你应该返回 2->1->4->3.
解法
- 递归法
先复习下递归法：
在函数定义中使用函数自身的方法。也就是函数调用自身。
如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归（避免无限循环）就可以解决的地步。
回到题目：
1.首先将问题拆解成子问题
1->2->3->4 ==> 2->1->4->3
拆分成 交换1->2 和 交换3->4
交换后：2->1 和 4->3
只需要连接节点1和节点4即可
2.找到跳出递归的方法
当节点为null或它的next节点为null的时候，直接返回自身即可。
/*
* Created by johntsai on 2019-06-20
*/
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
/**
*
* 1->2->3
*
* 2->1->3
*
* 递归法：
* 1.两两交换：后一个指向前一个，前一个指向 后面交换之后返回的头节点的值（递归点）
* 2.节点为null，或节点只有一个，则直接返回（跳出递归的方法）
*
*/
class Solution {
fun swapPairs(head: ListNode?): ListNode? {
if(head?.next == null){
return head
}
val after = head.next
val next = after!!.next
after.next = head
head.next = swapPairs(next)
return after
}
}
fun main(args: Array<String>) {
val solution = Solution()
val node1 = ListNode(1)
val node2 = ListNode(2)
val node3 = ListNode(3)
val node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
printNode(node1)
val reverse = solution.swapPairs(node1)
printNode(reverse)
}
fun printNode(node: ListNode?){
var temp = node
val sb = StringBuilder()
while (temp != null) {
sb.append("[node:${temp.`val`}]")
temp = temp.next
if(temp != null) {
sb.append("->")
}
}
println(sb.toString())
}
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
2.迭代法
能用递归解决的问题，一般都能用非递归的方法解决。
比如这道题，可以自己先画出节点交换的示例图来方便自己理解，避免理不清各个节点如何交换。
为了方便我们操作，我们新建一个dummy节点在链表最前面。
只要理清节点之间的指向关系，这道题目就不难解答出。
class Solution2 {
fun swapPairs(head: ListNode?): ListNode? {
var prev: ListNode?
val dummy = ListNode(0)
dummy.next = head
prev = dummy
while (prev?.next != null && prev.next!!.next!= null) {
val first = prev.next
val second = prev.next!!.next
prev.next = second
first!!.next = second!!.next
second.next = first
prev = first
}
return dummy.next
}
}
