一、题目简介

反转一个单链表。

示例:

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

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

题目地址：https://leetcode.com/problems/reverse-linked-list/submissions/

二、解法

1、保留原有的链表结构不变

func reverseList(head *ListNode) *ListNode {
    //如果一个节点或为空，直接返回
	if head == nil || head.Next == nil {
		return  head
	}

	var curNode *ListNode = head //头节点
	var newList *ListNode //每次放到最开头的位置

	for {
		var newNode = ListNode{}
		newNode.Val = curNode.Val

		if newList != nil{
			// 插入开始的问题
			newNode.Next = newList
		} else {
			//第一个节点
			newNode.Next = nil
		}

		newList = &newNode

		if curNode.Next == nil {
			break
		}
		curNode = curNode.Next
	}

	return newList
}

2、在原有的链表上修改

func reverseList(head *ListNode) *ListNode {
   if head == nil || head.Next == nil{
      return  head
   }
   beforeNode := head
   nextNode := head.Next

   for  {
      if nextNode == nil {
         break
      }
      //交换nextNode
      next2Node := nextNode.Next
      nextNode.Next = beforeNode
      beforeNode = nextNode

      nextNode = next2Node
   }
   head.Next = nil
   head = beforeNode

   return  head
}