反转链表

题目描述

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

样例

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

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

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) {
        ListNode *pre=nullptr; //定义一个空指针
        auto cur=head; //把头驱节点先存到cur
        while(cur){  
            auto t=cur->next;  //因为下面的操作会改变cur的下一个节点，所以需要先存下cur的下一个节点
            cur->next=pre;  //让cur的下一个指针往回指
            pre=cur;  //pre存下当前节点，让后面的节点指向pre
            cur=t;  //遍历下一个节点
        }
        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 || !head->next) return head;  //如果链表为空或者链表就一个节点就直接返回
        auto p=head,q=p->next;  //把前两个节点分别赋给p和q
        while(q){
            auto o=q->next;  //先把q的下一个节点存下来
            q->next=p;  //把q指向p
            p=q,q=o;  //p和q依次向后移动一位
        }
        head->next=nullptr;  //把head的下一个节点设空指针
        return p; //因为遍历完链表的节点后p在最后一个位置 比如 4->5->空   此时 p=5,q=空
    }
};

递归，个人感觉递归容易理解

/**
 * 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 || !head->next) return head;
        ListNode *tail=reverseList(head->next); 
        head->next->next=head;  //指向前面节点在指向自己
        head->next=nullptr;  //防止出现链表环
        return tail;
    }
};