206. Reverse Linked List

Leetcode 链接

题目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

题意解析

反转链表

解决方案一：遍历法

Go 代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil
    for head != nil {
        tmp := head.Next
        head.Next = prev
        prev = head
        head = tmp
    }

    return prev
}

解决方案二：递归法

Go 代码

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

    p := reverseList(head.Next)

    head.Next.Next = head
    head.Next = nil
    return p
}