LeetCode习题：反转链表

题目描述：反转一个单链表。

示例：

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

题解一：双指针

解题思路：遍历链表的同时，prev指针保持指向反转后链表的头节点，pcur指针沿着链表移动，移动的同时，将pcur当前指向的节点插入到prev之前，prev重新指向最新头结点，pcur继续移动，直到链表尾部结束

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if (head == nil || head?.next == nil) {
            return head
        }
        // 哨兵节点
        let sentinel = ListNode(-1)
        sentinel.next = head
        var prev = sentinel.next
        var pcur = prev?.next
        while(pcur != nil) {
            prev?.next = pcur?.next
            pcur?.next = sentinel.next
            sentinel.next = pcur
            pcur = prev?.next
        }
        return sentinel.next
    }
}

优化写法

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode?
        var pcur = head
        while(pcur != nil) {
            let next = pcur?.next
            pcur?.next = prev
            prev = pcur
            pcur = next
        }
        return prev
    }
}

复杂度分析

时间复杂度：O(n), n为链表长度，需要遍历整个链表

空间复杂度：O(1)，未额外申请存储空间

题解二：递归 (LeetCode官方题解）

解题思路：递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？假设链表为：

n1→…→nk−1→nk→nk+1→…→nm→∅

若从节点 nk+1 到 nm已经被反转，而我们正处于 nk。

n1→…→nk−1→nk→nk+1←…←nm

我们希望 nk+1的下一个节点指向 nk。所以，

nk.next.next=nk。

需要注意的是 n1下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if (head == nil || head?.next == nil) {
            return head
        }
        let newHead = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return newHead
    }
}

复杂度分析

时间复杂度：O(n), 其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n), 其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

题目来源：LeetCode