206.E 反转链表

Problem: 206. 反转链表

思路

思路1：递归。先反转从第二个节点开始的其他节点，然后再把第一个节点放到最后。

思路2：从第二个节点开始遍历，依次把cur.next指向preHead。最后需要记得把head.next指向nil

Code

代码1：

func reverseList(head *ListNode) *ListNode {
	// 为避免空指针问题，此处应该包含head.Next == nil的情况
	if head == nil || head.Next == nil {
		return head
	}

	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil //把原头结点的next指向nil，避免成环
	return newHead
}

代码2：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
	// 为避免空指针问题，此处应该包含head.Next == nil的情况
	if head == nil || head.Next == nil {
		return head
	}

	preHead := head
	cur := head.Next
	for cur != nil {
		next := cur.Next //暂存下一个节点
		cur.Next = preHead
		preHead = cur
		cur = next
	}
	head.Next = nil
	return preHead
}