力扣 206反转链表

反转一个单链表。

示例:

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

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

1.利用外部条件 容器

一开始想到的就是这种方法

具体实现就是想链表放进容器中，利用容器的函数完成操作

也可以用栈，将元素压栈，利用栈先进后出的特性，将头指针依次指向出栈节点。

代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<ListNode *>s;
     
        for(ListNode *p=head;p;p=p->next)//入栈 从头结点开始入
        {
            s.push(p);
        }
        ListNode *l=new ListNode(-1);//创建新表的预先指针 也可以在原表基础上建 但是没成功 l不动
        ListNode *cur=l;//当前指针 动
        while(!s.empty())
        {
           // cur->next=new ListNode(0);
            cur->next=s.top(); //指向栈顶元素 
            cur=s.top();//指针下移 栈顶是表尾，栈底是表头所有这样表示
            s.pop();//出栈
        }
        cur->next=NULL;//尾指向空
        return l->next;//返回头结点
    }
};
           

2.双指针 迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p=NULL;//新表首结点，初始化为null，使新表指向null
       ListNode *next=NULL;//下一个元素
       while(head)
       {
           next=head->next;//下一个结点
           head->next=p;//当前结点链接p p=null，则将这个结点摘出
           p=head;//p指向当前结点，当前结点成为新表首结点
           head=next;//head指向旧表的下一个结点
           
       }
       return p;
    }
};
           

图解：http://www.pianshen.com/article/517476376/

3.递归

假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？

列表nk-2 nk-1 nk nk+1 nk+2 。。。。

正处于nk若反转 使nk+1指向nk 则需

head->next->next=head;

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        ListNode *p=reverseList(head->next);
       head->next->next=head;
       head->next=NULL;
       return p;
    }
};
           

三种方法整体效率对比：基本没差