leetcode 206. Reverse Linked List(剑指offer16)、

无论是1，还是2，删除链表都需要3个节点，只是现在这种最新写法只把cur作为了判断循环的依据，并且下一个节点的生成放在循环内。

206. Reverse Linked List

之前在牛客上的写法：

错误代码:

class Solution {

public:

    ListNode* ReverseList(ListNode* pHead) {

        if(pHead == NULL)

            return NULL;

        ListNode* p1 = pHead;

        ListNode* p2 = pHead->next;

        ListNode* p3 = pHead->next->next;

        pHead->next = NULL;

        while(p3 != NULL){

            p2->next = p1;

            p1 = p2;

            p2 = p3;

            p3 = p3->next;

        }

        p2->next = p1;

        return p2;

    }

};

此代码会报“段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起”

如果链表只有一个节点，那p2就是空指针，p3就是空指针的下一个指针，但空指针是没有next的

正确代码:

class Solution {

public:

    ListNode* ReverseList(ListNode* pHead) {

        if(pHead == NULL)

            return NULL;

        else if(pHead->next == NULL)

            return pHead;

        ListNode* p1 = pHead;

        ListNode* p2 = pHead->next;

        ListNode* p3 = pHead->next->next;

        pHead->next = NULL;

        while(p3 != NULL){

            p2->next = p1;

            p1 = p2;

            p2 = p3;

            p3 = p3->next;

        }

        p2->next = p1;

        return p2;

    }

};

个人觉得这种以当前节点为循环判断条件的方式比较好：

class Solution {

public:

    ListNode* reverseList(ListNode* head) {

        ListNode* pre = NULL;

        while(head){

            ListNode* tmp = head->next;

            head->next = pre;

            pre = head;

            head = tmp;

        }

        return pre;

    }

};

92. Reverse Linked List II

依旧要在循环开始前获得pre和cur指针。

有个边界条件是m = 1的时候，可能第一个节点，即head指针也要反转，所以返回的时候返回head会出错。所以申请了一个指针，并且下一个节点就是head，这样无论哪种情况，都是申请指针的下一个节点。

注意pre的初始化也是在head之前，因为m <= 1实际上都是在head之前。还要注意m-1的设置，并且这个for循环就是找pre的位置。

i=m;i < n 比如3个节点的reverse，实际上只用操作2次就好了。

思路上：每次把cur的下一个节点旋转到cur之前去，pre节点实际上是不变的。

错误写法：

错误在tmp->next = cur; 第一次循环是对的，后面的就错了。cur指针是不变的，但是pre和cur之间的个数在增加，真正要放的位置是pre后面

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

        ListNode* pre = new ListNode(-),*res = pre;

        pre->next = head;

        res = pre;

        for(int i = ;i < m - ;i++)

            pre = pre->next;

        ListNode* cur = pre->next;

        for(int i = m;i < n;i++){

            ListNode* tmp = cur->next;

            cur->next = tmp->next;

            tmp->next = cur;

            pre->next = tmp;

        }

        return res->next;

    }

};

正确写法：

class Solution {

public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {

        ListNode* pre = new ListNode(-),*res = pre;

        pre->next = head;

        res = pre;

        for(int i = ;i < m - ;i++)

            pre = pre->next;

        ListNode* cur = pre->next;

        for(int i = m;i < n;i++){

            ListNode* tmp = cur->next;

            cur->next = tmp->next;

            tmp->next = pre->next;

            pre->next = tmp;

        }

        return res->next;

    }

};

巴特西

leetcode 206. Reverse Linked List(剑指offer16)、

最新文章

热门文章