题目

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

TAG：

Linked List

代码

1.迭代解法：(iteratively,效率较高)

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode reverseList(ListNode head) {
11         if(head==null)
12             return null;
13         ListNode p=head,pNext=null,pFormer=null;//pFormer->p->pNext
14         while(p!=null){
15             pNext = p.next; //暂存下一个节点，作为倒序后的前序节点
16             p.next = pFormer; //p指向倒序后的后序节点，若是head节点则指向null
17             pFormer = p;//当前节点作为下一个节点的前序节点
18             p = pNext;//节点指针后移
19         }
20         return pFormer;//最后节点指针后移到null时，退出while循环，此时pFormer指向链表最后一个元素（新链表第一个元素）
21     }
22 }

2.递归解法:(recursively,效率较低)

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     
11     ListNode pFormer=null; 
12     public ListNode reverseList(ListNode head) {
13         if(head==null)
14             return null;
15         ListNode pNext=null;
16         pNext = head.next;  
17         head.next = pFormer;  
18         pFormer = head; 
19         reverseList(pNext);
20         return pFormer;
21     }
22 }

__________________________________________________________ shoobie do lang lang ^^