剑指 Offer 24. 反转链表

easy

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

三指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 三指针
func reverseList(head *ListNode) *ListNode {
	var prev, next *ListNode // 默认为nil
	cur := head
	for cur != nil {
		next = cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}
	return prev
}

递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 递归
func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList2(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}