Leetcode206.反转链表(HOT100)

链接：

我的代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p = head;
        ListNode*res = new ListNode(-1);
        while(p){
            ListNode*k = res->next;
            res->next = p;
            p = p->next;
            res->next->next = k;
        }
        return res->next;
    }
};

我用的是迭代实现。 

更好的代码： 

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)return nullptr;
        ListNode* a = head,*b = head->next;
        while(b){
            ListNode*c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        head->next = nullptr;
        return a;
    }
};

第一步：

第二步：
 

最后一步：
 

此时，别忘了，head仍然指向原来的头结点，这个头结点现在是尾节点了，所以把它的next置空。

 更好的代码（递归实现）：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next)return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

 图示：

 

 

上图是head->next->next = head;

完毕。 

 

 

原文地址：https://blog.csdn.net/kitesxian/article/details/143925881

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！