菜鸟系列 Golang 实战 Leetcode —— 面试题24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。   示例: ``` 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL   限制： 0 <= 节点个数 <= 5000 ``` 题解： + 采用原地反转的方式进行反转 这里假设存在旧链表head： 1->2->3->4->nil; 此时定义一个新链表 newHead；进行原地反转，首先反转节点 1： next=head.next; head.next=newHead; newHead=head; head=next；经过此轮反转 新链表为1->nil;旧链表为 2->3->4->nil ;此时循环执行即可完成反转。 ``` func reverseList(head *ListNode) *ListNode { // 原地反转 if head==nil||head.Next==nil{ return head } var newHead *ListNode var next *ListNode for head!=nil{ next=head.Next head.Next=newHead newHead=head head=next } return newHead } ``` + 采用递归的方式 思路，大致是 反转 下一个节点，然后当前节点的下一个节点的下一个节点为原来的头节点，原来的头节点的下一个节点为空 ``` func reverseList(head *ListNode) *ListNode { // 递归反转 if head==nil||head.Next==nil{ return head } newHead:=reverseList(head.Next) head.Next.Next=head head.Next=nil return newHead } ```