LeetCode-206.反转链表 - sheep44044的小站

链表#

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1
输入：head = [1,2,3,4,5]
2
输出：[5,4,3,2,1]

示例 2：

1
输入：head = [1,2]
2
输出：[2,1]

示例 3：

1
输入：head = []
2
输出：[]

双指针的解法

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func reverseList(head *ListNode) *ListNode {
9
    var pre *ListNode
10
    cur := head
11
    for cur != nil {
12
        next := cur.Next
13
        cur.Next = pre
14
        pre = cur
15
        cur = next
16
    }
17

18
    return pre
19
}

递归的方法

1
func reverseList(head *ListNode) *ListNode {
2
    return help(nil, head)
3
}
4

5
func help(pre, head *ListNode)*ListNode{
6
    if head == nil {
7
        return pre
8
    }
9
    next := head.Next
10
    head.Next = pre
11
    return help(head, next)
12
}