算法：逆转链表

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list

解答

分析

这道题是经典链表题目，可以用迭代和递归两种不同的思路来进行解决

解答一：使用迭代

思路

这个方法要使用到三个指针，第一个指向前一个节点，第二个指向当前节点，第三个指向下一个节点。每次把当前节点的next指针指向前一个节点，然后把三个指针往后移动，重复直到完成逆转。

代码

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if (head==null) return null
        if (head.next==null) return head
        var pre : ListNode? = null
        var current : ListNode? = head
        var next : ListNode? = head.next

        while (next!=null){
            val temp : ListNode? = next.next
            current?.next = pre
            pre = current
            current = next
            next = temp
        }
        current?.next = pre
        return current
    }
}

解答二：使用递归

思路

递归相比迭代思维比较容易想一点，代码也比较简单。但是会占用更多的空间。我们可以假设链表分为两段，前一段已经逆转完成，后一段递归进行逆转，然后把后一段的指针指向前一段即可

代码

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        return point(null,head)
    }

    fun point(pre:ListNode?,current:ListNode?):ListNode?{
        if (current==null) return pre
        val next = current.next
        current.next = pre 
        return point(current,next)
	}
}

小结

刚开始做的时候在指针这一块出现了一点小问题，在考虑是用几个指针，如何进行迭代等。这道题难度不高，但是要熟练掌握两种不同做法