第 2 日：反转链表

题目链接：

题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

0 <= 节点个数 <= 5000

解题

1. 递归方式 大致思路： 反转链表逻辑上很简单，但最需注意的一点是变更next指向上一个节点后，我们无法再寻找链表原来的next结点。 而递归正好可以完美的帮我们克服这个困难，当递归遍历时，遍历的最后一个结点符合条件时会结束递归，此时会自动回溯上一个方法，也就相当于找到了上一个结点。这不就so so so so easy了？ 详细代码如下： public ListNode reverseList(ListNode head) { if (head==null) return null; ListNode newHead = toHeadReverse(head); head.next=null;//避免循环，所以去掉下一个指向节点 return newHead; } public ListNode toHeadReverse(ListNode node){ if (node.next==null) return node;//遍历到最后一个结点时返回此节点，这个节点表示新的头结点以后会用到 ListNode head = toHeadReverse(node.next); node.next.next=node;//将下一个节点的next指向自己 return head;//返回新头结点 }
2. 使用非递归 大致思路： 递归会大量占用内存空间，所以我们看看非递归是否能完美解决呢； 使用三个指针（p、c、n）， 在改变当前节点next指向之前，现将next存到指针n中，然后改变当前结点（指针c）next指向（指向上一个指针p）， 详细代码如下： public ListNode reverseList(ListNode head){ ListNode p=null;//上一个节点 ListNode c=null;//保存当前结点 ListNode n=head;//下一个结点 while (n!=null){ c=n; n=n.next; c.next=p; p=c; } return c; }