反转一个单链表。
进阶:
链表可以迭代或递归地反转。你能否两个都实现一遍？
详见：https://leetcode.com/problems/reverse-linked-list/description/
Java实现：
迭代实现：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
ListNode cur=head;
ListNode pre=null;
ListNode next=null;
while(cur!=null){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
递归实现：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode p=head;
head=reverseList(p.next);
p.next.next=p;
p.next=null;
return head;
}
}
C++实现:
方法一：非递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr)
{
return nullptr;
}
ListNode *cur=head;
ListNode *pre=nullptr;
ListNode *next=nullptr;
while(cur)
{
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
方法二：递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr||head->next==nullptr)
{
return head;
}
ListNode *p=head;
head=reverseList(p->next);
p->next->next=p;
p->next=nullptr;
return head;
}
};
参考：https://www.cnblogs.com/grandyang/p/4478820.html