反转链表

ryluo 2020-06-27 13:37:03

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

思考题:

样例

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

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

分析:

迭代:

反转链表的核心思路就是将当前节点指向其前继节点。那么可以定义一个NULL的前继节点,然后遍历整个链表,不断地将当前节点指向其前继节点,但是需要注意地是,在将当前节点指向前继节点之前需要先把当前节点地next节点保存,不然就无法遍历后续地节点。

递归:

  1. 递归边界:如果head或者head->next为NULL,返回head

    image-20200627141311742

/**
 * 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;
        while(cur){
            auto 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 || !head->next) return head;
        ListNode* tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};