反转链表

反转一个单链表。

示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路:

在遍历列表时，将当前节点的 head.Next 指针改为指向prev

1->2->3->4->5->NULL
NULL<-1<-2<-2<-4<-5

代码:

// 迭代
type ListNode struct {
   Val  int
   Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
   var temp *ListNode
   var prev *ListNode = nil
   for ; head != nil; {
      temp = head.Next
      head.Next = prev
      prev = head
      head = temp
   }
   return prev
}

递归解法很难用语言描述，我大概模拟一下递归过程，太巧妙了

// 递归
func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	last := reverseList2(head.Next)
	println(head.Val, last.Val)
	head.Next.Next = head
	head.Next = nil
	return last
}

reverseList(1->2->3->4->5->nil)
         
         revreverseList(2->3->4->5->nil)				 

                  reverseList(3->4->5->nil)			          
          
                           reverseList(4->5->nil)				                  
                   
                                    reverseList(5->nil)
                                    head = 5->nil
                                    return last = head
                                
                           head = 4->5->nil
                           head.Next.Next = head // 5.Next -> 4
                           head.Next = nil       // 4.Next -> nil
                           return last = 5->4->nil
                       
                  head = 3->4<-5
                            |
                           nil
                  head.Next.Next = head // 4.Next -> 3
                  head.Next = nil       // 3.Next -> nil
                  return last = 5->4-3->nil
         
         head = 2->3<-4<-5
                   |
                  nil
         head.Next.Next = head // 3.Next -> 2
         head.Next = nil       // 2.Next -> nil
         return last = 5->4-3->2->nil

head = 1->2<-3<-4<-5
          |
         nil
head.Next.Next = head // 2.Next -> 1
head.Next = nil       // 1.Next -> nil
return last = 5->4-3->2->1->nil