剑指Offer:反转列表(24)

题目描述:

输入一个链表，反转链表后，输出新链表的表头。

解题思路:

比较简单,直接上代码

递归:

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3         //递归终止条件是当前为空，或者下一个节点为空
 4         if(head==null || head.next==null) {
 5             return head;
 6         }
 7         //这里的cur就是最后一个节点
 8         ListNode cur = reverseList(head.next);
 9         //这里请配合动画演示理解
10         //如果链表是 1->2->3->4->5，那么此时的cur就是5
11         //而head是4，head的下一个是5，下下一个是空
12         //所以head.next.next 就是5->4
13         head.next.next = head;
14         //防止链表循环，需要将head.next设置为空
15         head.next = null;
16         //每层递归函数都返回cur，也就是最后一个节点
17         return cur;
18     }
19 }

迭代:

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3         //申请节点，pre和 cur，pre指向null
 4         ListNode pre = null;
 5         ListNode cur = head;
 6         ListNode tmp = null;
 7         while(cur!=null) {
 8             //记录当前节点的下一个节点
 9             tmp = cur.next;
10             //然后将当前节点指向pre
11             cur.next = pre;
12             //pre和cur节点都前进一位
13             pre = cur;
14             cur = tmp;
15         }
16         return pre;
17     }
18 }