每天一道LeetCode题——两两交换链表中的节点

前言

上一篇文章给自己立了一个大大的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

    }
}