LeetCode OJ Algorithm – reverse linked list ii (medium)

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:

Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

地址

https://leetcode.com/problems/reverse-linked-list-ii/

程序范例

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
            ListNode* chead = head;
            int data[10000] = {}; 
            for (int i = 0; i < n; i++) { data[i] = chead->val;
                chead = chead->next;
            }  
            
            int mid = (m + n)>>1;
            for (int left = m - 1; left <= mid - 1; left++) {
                int right = (n - 1) - (left - (m - 1));
                if (right <= left) {
                    // while up to the mid index
                    break;
                }
                int tmp = data[left];
                data[left] = data[right];
                data[right] = tmp;
            }
            
            
            chead = head;
            for (int i = 0; i < n; i++) {
                std::cout<<data[i]<<std::endl;
            }
            
            for (int i = 0; i < n; i++) { if (i >= m - 1) {
                    chead->val = data[i];
                }
                chead = chead->next;
            }
           
            return head;
    }
};

时间复杂度

O(n^3)


文章来源:胡旭博客 => LeetCode OJ Algorithm - reverse linked list ii (medium)

转载请注明出处,违者必究!


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法 | 标签: , , , , , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。