一、题目简介

反转一个单链表。

示例:

输入: 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 reverse(pHead *ListNode)  *ListNode{
   if pHead == nil || pHead.Next == nil {
      return pHead
   }

   var newHead *ListNode
   for pHead != nil {
      nextNode := pHead.Next

      pHead.Next = newHead
      newHead = pHead
      pHead = nextNode
   }

   return newHead
}