206.md

Question:

Reverse a singly linked list.

Example:

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

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

Analysis

reverseList 实际上跟reverseList2是等价的，只是reverseList更加巧妙，将头结点的情况恰好包含在内，因而十分简洁

Tips

Code

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
        var current, pre, next *ListNode
        current = head
        for current != nil {
                next = current.Next
                current.Next = pre
                pre = current
                current = next
        }
        return pre
}

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

        var front, middle, back *ListNode
        front = head
        middle = head.Next
        back = middle.Next
        for back != nil {
                middle.Next = front
                front = middle
                middle = back
                back = back.Next
        }
        head.Next = nil
        middle.Next = front
        return middle
}