题目描述：反转一个单链表。
示例：
输入: 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 层。
