设为首页 加入收藏

TOP

leadcode的Hot100系列--206. 反转链表
2019-07-02 14:12:28 】 浏览:24
Tags:leadcode Hot100 系列 --206. 反转

这里使用两种方式,
一个是直接从头往后遍历 -------> 迭代
一个是从最后一个往前遍历 -----> 递归

迭代

定义三个变量:pPre pNext pNow
pPre表示当前节点的前一个地址,pNext表示当前节点的下一个地址,pNow表示当前节点的地址。

反转的核心:就是把 pNow的next指针,指向 pPre

因为反转之后,pNow的next原来的值会丢,所以在反转之前,要用pNext把原来的值保存一下。
反转之后,要处理下一个节点,而本节点就是下一个节点的前一个节点,所以用pPre把当前节点地址保存一下。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *pstPre = NULL;
    struct ListNode *pstNow = head;
    struct ListNode *pstNext = NULL;
    
    while (NULL != pstNow)
    {
        pstNext = pstNow->next;  // 先保存一下当前节点的next指针
        pstNow->next = pstPre;    // 做反转
        pstPre = pstNow;              // 更新pstPre指针
        pstNow = pstNext;            // 继续做下一个节点的反转
    }
    return pstPre;
}

递归

递归的话,不太好理解,先上代码,看着代码来理解:

struct ListNode* reverseList(struct ListNode* head){
    struct ListHode *pstNewHead = NULL;
    if (head == NULL || head->next == NULL)   // 如果链表为空,或者是最末端节点,则直接返回当前节点地址
    {
        return head;
    }
    else
    {
        pstNewHead = reverseList(head->next);  // 返回新链表头节点
        head->next->next = head;  // 这里完成反转
        head->next = NULL;
        
        return pstNewHead;
    }
}

递归写法的关键是:head->next->next = head 这句代码中,
head 是谁,head->next 是谁,head->next->next 又是谁!

可以从后往前理解,假设有三个节点,为 1 -> 2 -> 3,

最后一次:当head为节点2时,入参为传入节点3,节点3的next为NULL,返回节

点3的地址。

此时:head指向节点2,pstNewHead指向节点3,
-----> 得到:head->next 指向节点3,head->next->next 就相当于节点3的next,
所以:执行完 "head->next->next = head"之后,就相当于把节点3的next指向了节点2,完成一个反转。
而节点2的next指针已经没用了(原本节点2的next指向了节点3),直接指向NULL。
上面部分实现了节点3与节点2的反转,并此时pstNewHead指向了节点3。

再继续。
上面返回pstNewHead为节点3的地址,此时入参的head为1(因为之前head为节点2,返回调用者的时候,是head->next为节点2,所以这里调用者为节点1),
所以,head->next为2,head->next->next 就相当于是节点2的next,所以执行完 "head->next->next = head"之后,就相当于把节点2的next指向了节点1
而节点1原来的next没用了(原本节点1的next指向了节点2),直接指向NULL,这里就相当于是链表尾部。
然后返回pstNewHead。
其实这里pstNewHead只赋值过一次,之后从未改变,一直指向了最一开始的节点3。


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇linux 广播和组播 下一篇leadcode的Hot100系列--226. 翻转..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }