206. 反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

⭐ 双指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var pre, cur *ListNode = nil, head
	for cur != nil {
		tmp := cur.Next
		cur.Next = pre
		pre = cur
		cur = tmp
	}
	return pre
}

递归

实质上和双指针一样

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func reverseList(head *ListNode) *ListNode {
	var reverse func(pre, cur *ListNode) *ListNode
	reverse = func(pre, cur *ListNode) *ListNode {
		if cur == nil {
			return pre
		}
		after := cur.Next
		cur.Next = pre
		return reverse(cur, after)
	}
	return reverse(nil, head)
}

另一种递归

很妙啊

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func reverseList(head *ListNode) *ListNode {
   if head == nil {
      return nil
   }
   if head.Next == nil {
      return head
   }
   last := reverseList(head.Next)
   head.Next.Next = head // 翻转头节点与第二个节点的指向
   head.Next = nil
   return last
}