题目

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

示例:

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

题解

思路一（迭代）

遍历链表时，修改节点next指向

• 暂存当前节点（cur）指向节点（next），用于作为下一个修改的节点
• 修改当前节点（cur）指向节点为前一节点（pre），此时cur反转完成
• pre更新为当前节点（cur）
• cur更新为暂存的下一节点（next）

思路二（递归）

• 使用当前节点（cur）和前一节点（pre）走至链表末端
• cur为nil时，递归结束，且cur为反转之后链表的head
• 将cur的next指向pre

代码

迭代

func reverseList(head *ListNode) *ListNode {
	var pre *ListNode = nil
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

递归

func reverseList(head *ListNode) *ListNode {
	return reverse(head, nil)
}

func reverse(cur, pre *ListNode) *ListNode {
	if cur == nil {
		return pre
	}
	ret := reverse(cur.Next, cur)
	cur.Next = pre
	return ret
}