leetcode92

    技术2023-05-14  98

    刷题主页

    反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

    这道题是普通反转链表的升级版,这次只是反转链表中间的一部分,而不是全部反转,掌握了普通的反转链表后,这道题可以很快写出,我们需要找到将要反转部分的起止位置,并将其反转,注意反转位置可能是第一个结点,因此需要一个哑结点做辅助。

    class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if(!head || !head->next)return head; ListNode* dummy=new ListNode(-1); dummy->next=head; ListNode* cur=dummy; ListNode* start; ListNode* end; for(int i=1;i<=n;++i){ if(i==m){ start=cur; } cur=cur->next; } end=cur; start->next=reverseList(start->next,end->next); return dummy->next; } ListNode* reverseList(ListNode* start,ListNode* end){ ListNode* pre=end; ListNode* cur=start; while(cur!=end){ ListNode* temp=cur->next; cur->next=pre; pre=cur; cur=temp; } return pre; } };
    Processed: 0.019, SQL: 12