前言
上一篇文章給自己立了一個(gè)大大的flag浇冰。自己立的flag，跪著也要完成聋亡。
有時(shí)候會(huì)想肘习，算法題這么難，為啥要折磨自己呢坡倔？我覺得在做算法題的過程中漂佩，
- 能解決眼高手低的問題，心里想的是一套致讥，真正實(shí)踐起來可能有這樣那樣的問題仅仆。聰明的古人有詩為證
紙上得來終覺淺，絕知此事要躬行
- 鍛煉了編碼的嚴(yán)謹(jǐn)性垢袱。為了看到大大的Accepted墓拜，必須要考慮到各種可能性。
- 前面說的都很虛请契，最終還是為了面試的時(shí)候咳榜，能胸有成竹點(diǎn)，不被刷掉爽锥。（想起了Homebrew作者 Max Howell 大神在面試Google的時(shí)候涌韩，因?yàn)椴粫?huì)在白板上翻轉(zhuǎn)二叉樹被拒了，連這種級別的大神也會(huì)因?yàn)樗惴}被拒氯夷，只能說Google太死板了臣樱，可能大公司就是這樣吧）
話不多說，開始今天的解題。
題目
給定一個(gè)鏈表雇毫，兩兩交換其中相鄰的節(jié)點(diǎn)玄捕，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值棚放，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換枚粘。
示例
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
解法
- 遞歸法
先復(fù)習(xí)下遞歸法：
在函數(shù)定義中使用函數(shù)自身的方法。也就是函數(shù)調(diào)用自身飘蚯。
如何實(shí)現(xiàn)調(diào)用自身的函數(shù)馍迄。訣竅在于，每當(dāng)遞歸函數(shù)調(diào)用自身時(shí)局骤，它都會(huì)將給定的問題拆解為子問題攀圈。遞歸調(diào)用繼續(xù)進(jìn)行，直到到子問題無需進(jìn)一步遞歸（避免無限循環(huán)）就可以解決的地步庄涡。
回到題目：
1.首先將問題拆解成子問題
1->2->3->4 ==> 2->1->4->3
拆分成 交換1->2 和 交換3->4
交換后：2->1 和 4->3
只需要連接節(jié)點(diǎn)1和節(jié)點(diǎn)4即可
2.找到跳出遞歸的方法
當(dāng)節(jié)點(diǎn)為null或它的next節(jié)點(diǎn)為null的時(shí)候量承，直接返回自身即可。
/*
* 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.兩兩交換：后一個(gè)指向前一個(gè)穴店，前一個(gè)指向 后面交換之后返回的頭節(jié)點(diǎn)的值（遞歸點(diǎn)）
* 2.節(jié)點(diǎn)為null撕捍，或節(jié)點(diǎn)只有一個(gè)，則直接返回（跳出遞歸的方法）
*
*/
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.迭代法
能用遞歸解決的問題泣洞，一般都能用非遞歸的方法解決忧风。
比如這道題，可以自己先畫出節(jié)點(diǎn)交換的示例圖來方便自己理解球凰，避免理不清各個(gè)節(jié)點(diǎn)如何交換狮腿。
為了方便我們操作，我們新建一個(gè)dummy節(jié)點(diǎn)在鏈表最前面呕诉。
只要理清節(jié)點(diǎn)之間的指向關(guān)系缘厢，這道題目就不難解答出。
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
}
}
