leetcode_206. 反转链表

One minute read
LeetCode
面试 • 算法 • 数据结构

反转链表

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

遍历和递归

遍历

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    p := head.Next // 工具人游标
    head.Next = nil // 摘下头节点准备迎接
    for p != nil {
        tmp := p.Next // 作好后期计划
        p.Next = head // 斩断后继无牵挂
        head = p      // 抢回第一把交椅
        p = tmp       // 重拾信心，继续前进

        // 丧心病狂的写法：
        // p.Next, head, p = head, p, p.Next
    }
    return head
}

// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2.5 MB, 在所有 Go 提交中击败了100.00%的用户

向着header前进！！！！

丧心病狂

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    p := head.Next // 工具人游标
    head.Next = nil // 摘下头节点准备迎接
    for p != nil {
        // h  p
        // 1->2->3->4
        // 丧心病狂的写法：
        p.Next, head, p = head, p, p.Next
        // 一个个来，p后面接上h，h回到p，p前进
    }
    return head
}

// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2.5 MB, 在所有 Go 提交中击败了100.00%的用户

递归

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    cur := reverseList(head.Next)
    head.Next.Next, head.Next = head, nil
    return cur
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :2.9 MB, 在所有 Go 提交中击败了22.90%的用户

分享：