当先锋百科网

首页 1 2 3 4 5 6 7

新建链表头插入方法

这种方法需要额外新建一个链表,然后利用头插,依次将head的节点插入到新建的节点当中,实现反转。

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

详解:
在这里插入图片描述

迭代双指针

此算法需要设置两个节点指针,一前一后,调转链表中节点的指向,直到遍历完指针的所有节点。

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

迭代双指针错误版本

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *pre=head;//如果这样翻转之后的链表最后一个节点不会指向NULL
        ListNode *cur=head->next;//同理
        while(pre!=NULL)//此处的终止条件错误,应该是cur!=NULL
        {
            ListNode *p=cur;
            cur->next=pre;
            pre=p;
            cur=p->next;
        }
        return pre;
    }
};

详解:
在这里插入图片描述

递归

递归的三个条件:
1、可以分解为子问题
2、子问题求解方式和原问题一致
3、存在终止递归条件,最小子问题
可以理解为子问题,即反转由头节点和除了头节点的其他节点组成的整体,那么就相当于对一个含有两个节点的链表进行反转。

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;
    }
};

在这里插入图片描述
此图片引用自
这里