美文网首页
算法题92:反转链表

算法题92:反转链表

作者: 死亡中走出来 | 来源:发表于2021-06-05 13:02 被阅读0次

题目:

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

其实,看到这个题,我的想法是直接反转中间那块。看起来挺简单,思路也没有问题。直接做就OK了。其实,是错误的;看到链表的题,应该先脑袋里过下什么是链表,链表是干嘛的。

这道题,很清晰。

直接分成三段,前后不用管,直接反转中间部分即可。

于是,有了下面的答案。参考代码:

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
         // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
///链表向后移动left个,然后分割出第一个链表左边部分。
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
///中间部分,直接反转。
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
///返回结果
        return dummyNode->next;
    }
};

相关文章

网友评论

      本文标题:算法题92:反转链表

      本文链接:https://www.haomeiwen.com/subject/uasqeltx.html